动态规划专题

A. Helping People

神仙概率题

容易发现给定的区间限制满足树形关系,考虑建树。

个人认为最难理解的一点是,期望最大值并不是简单相加,所以直接设期望DP是很难做的。

设 $ a[i] $ 表示原来第 \(i\) 个人的钱数, $ dp[i][j] $ 表示第 \(i\) 个节点最大钱数小于等于 $ max{ a_k (k在区间i的范围之内) }+j $ 的概率。注意这里用小于等于,方便DP,最后统计答案再查分一下就好。

下面我们用 $ m[i] $ 代表 \(i\) 区间原有钱数的最大值, $ p[i] $ 代表该区间的接受概率。

可以得到状态转移方程

仔细理解一下这个方程,然后注意边界就好。复杂度 $ O(q^2) $

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100,M=5e3+100;
struct vjudge{
    int l,r,len,id,m;
    double p;
}sug[M];
struct edge{
    int to,next;
}e[M];
int n,q,a[N],cnt,head[M],depth[M],nleaf[M];
double dp[M][M],ans;
bool f[M];
bool cmp(vjudge a,vjudge b){
    return a.len<b.len;
}
inline double Max(double x,double y){
	if(x>y)return x;
	else return y;
}
void add(int u,int v){
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa){
    dp[u][0]=1-sug[u].p;
    depth[u]=depth[fa]+1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        dfs(v,u);
    }
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        dp[u][0]*=dp[v][sug[u].m-sug[v].m];
    }
    for(int i=1;i<=q;i++){
        double x=1,y=1;
        for(int j=head[u];j;j=e[j].next){
            int v=e[j].to;
            if(i+sug[u].m-sug[v].m>q)continue;
            x*=dp[v][min(i+sug[u].m-sug[v].m-1,q)];
            y*=dp[v][min(i+sug[u].m-sug[v].m,q)];
        }
        dp[u][i]=sug[u].p*x+(1-sug[u].p)*y;
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    int mm=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mm=max(mm,a[i]);
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%lf",&sug[i].l,&sug[i].r,&sug[i].p);
        sug[i].len=sug[i].r-sug[i].l+1;
        sug[i].id=i;
        int maxn=0;
        for(int j=sug[i].l;j<=sug[i].r;j++){
            maxn=max(maxn,a[j]);
        }
        sug[i].m=maxn;
    }
    sort(sug+1,sug+q+1,cmp);
    for(int i=1;i<=q;i++){
        for(int j=i+1;j<=q;j++){
            if(sug[i].l>=sug[j].l&&sug[i].r<=sug[j].r){
                add(j,i);
                nleaf[j]=1;
                f[i]=1;
                break;
            }
        }
    }
    ++q;
    sug[q]=(vjudge){1,n,n,q,mm,0};
    for(int i=1;i<q;i++){
        if(!f[i]){
            add(q,i);
        }
    }
    dfs(q,q);
    for(int i=0;i<q;i++){
    	if(i==0)ans+=dp[q][i]*(i+sug[q].m);
    	else 
    	ans+=(dp[q][i]-dp[q][i-1])*(i+sug[q].m);
	}
    printf("%0.9lf",ans);
}

B. Birds

简单背包

设 $ dp[i][j] $ 为走到第 \(i\) 棵树,抓了 \(j\) 只鸟剩余的最多魔法值。显然有:

注意两个边界。

  1. $ dp[i-1][j-k]<0 $ 一定要跳过,不然可能产生错解。

  2. $ dp[i-1][j-k]+X>W+b\times k $ 此时超出魔法上限。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int M=1e4+10;
int n,w,b,x,c[N],cost[N],dp[N][M];
int sum[N];
    
signed main()
{
    scanf("%d%d%d%d",&n,&w,&b,&x);
    for(int i=1;i<=n;i++){
        scanf("%lld",&c[i]);
        sum[i]=c[i]+sum[i-1];
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&cost[i]);
    }
    memset(dp,128,sizeof(dp));
    for(int i=0;i<=c[1];i++){
        dp[1][i]=w-cost[1]*i;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=c[i];j++){
            for(int k=0;k<=sum[i-1];k++){
                if(dp[i-1][k]<0)continue;
                if(dp[i-1][k]+x>w+b*k)
                    dp[i][k+j]=max(dp[i][k+j],w+b*k-cost[i]*j);
                else dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]-cost[i]*j+x);
            }
        }
    }
    for(int i=1;i<=sum[n]+1;i++){
        if(dp[n][i]<0){
            printf("%lld\n",i-1);
            return 0;
        }
    }
}

C. Positions in Permutations

我的做法可能看起来比较恶心,但本质上是一样的。

设 $ dp[i][j][x][y] $ 表示前 \(i\) 个数中选择 \(j\) 个作为好点, \(i-1\) \(i\) 的状态,其中0代表不是好点,1代表选择前一个位置,2代表选择后一个位置,这样可以得到一坨方程。(见代码

$ sum[i][j] $ 表示前 \(i\) 个位置,有 \(j\) 个好点的方案数,将空白位置全排列,得到的是至少有 \(j\) 个好点的方案数。

在利用二项式反演求解。复杂度 $ O(n^2) $

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1100;
const int mod=1e9+7;
int n,p,dp[N][N][3][3];
int sum[N][N];
int jc[N],ny[N];
inline int C(int x,int y){
    if(x<y)return 0;
    return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
signed main()
{
    scanf("%lld%lld",&n,&p);
    jc[0]=1;
    for(int i=1;i<N;i++){
        jc[i]=jc[i-1]*i%mod;
    }
    ny[0]=1;
    ny[1]=1;
    for(int i=2;i<N;i++){
        ny[i]=(mod-mod/i)*ny[mod%i]%mod;
    }
    for(int i=2;i<N;i++){
        ny[i]=ny[i-1]*ny[i]%mod;
    }
    sum[1][0]=dp[1][0][0][0]=1;
    if(n!=1)
    sum[1][1]=dp[1][1][0][2]=1;
    for(int i=2;i<=n;i++){
        sum[i][0]=dp[i][0][0][0]=1;
        for(int j=1;j<=i;j++){
            dp[i][j][0][0]=(dp[i-1][j][0][0]+dp[i-1][j][1][0]+dp[i-1][j][2][0])%mod;
            dp[i][j][1][0]=(dp[i-1][j][0][1]+dp[i-1][j][1][1]+dp[i-1][j][2][1])%mod;
            dp[i][j][2][0]=(dp[i-1][j][0][2]+dp[i-1][j][1][2]+dp[i-1][j][2][2])%mod;
            dp[i][j][0][1]=(dp[i-1][j-1][0][0]+dp[i-1][j-1][1][0])%mod;
            dp[i][j][1][1]=(dp[i-1][j-1][0][1]+dp[i-1][j-1][1][1])%mod;
            dp[i][j][2][1]=(dp[i-1][j-1][0][2]+dp[i-1][j-1][1][2])%mod;
            if(i!=n){
                dp[i][j][0][2]=(dp[i-1][j-1][0][0]+dp[i-1][j-1][1][0]+dp[i-1][j-1][2][0])%mod;
                dp[i][j][1][2]=(dp[i-1][j-1][0][1]+dp[i-1][j-1][1][1]+dp[i-1][j-1][2][1])%mod;
                dp[i][j][2][2]=(dp[i-1][j-1][0][2]+dp[i-1][j-1][1][2]+dp[i-1][j-1][2][2])%mod;
            }
            sum[i][j]=(sum[i][j]+dp[i][j][1][1])%mod;
            sum[i][j]=(sum[i][j]+dp[i][j][1][2])%mod;
            sum[i][j]=(sum[i][j]+dp[i][j][2][1])%mod;
            sum[i][j]=(sum[i][j]+dp[i][j][2][2])%mod;
            if(i>=j+1){
                sum[i][j]=(sum[i][j]+dp[i][j][0][1])%mod;
                sum[i][j]=(sum[i][j]+dp[i][j][0][2])%mod;
                sum[i][j]=(sum[i][j]+dp[i][j][1][0])%mod;
                sum[i][j]=(sum[i][j]+dp[i][j][2][0])%mod;
                if(i>=j+2)
                sum[i][j]=(sum[i][j]+dp[i][j][0][0])%mod;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            sum[i][j]=(sum[i][j]*jc[i-j])%mod;
        }
    }
    int ans=0;
    for(int i=p,j=1;i<=n;i++,j=-j){
        ans=(ans+j*sum[n][i]*C(i,p)%mod+mod)%mod;
    }
    cout<<ans<<endl;
}

H. Tavas in Kansas

题目背景让人感觉很纸张。

神奇博弈论

转换题面+一些技巧

  1. 我们最后想要的是两者得分的相对大小,由于两个人的得分不好同时维护,不妨将两人分数做差。

  2. 两人位置是不变的,跑最短路,距离离散化,将距离抽象成一个二维平面,以A的距离为横坐标,以B的距离为纵坐标,这样每个城市都映射到平面上。

  3. $ dp[i][j][0/1] $ 表示当前状态下 A行动(0)或B行动(1),这样最后结果不好确定,所以考虑倒序DP。

通过以上操作,我们发现题目简单多了,每次A会按照坐标按行取数,B按列取数,但不能没取到。 $ O(n^2)DP $ 即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2200,M=2e5+100;
const int inf=2e9;
int n,m,s,t,p[N],cnt,head[M],ns,nt,dp[N][N][2];
int dis[2][N];
int vals[N],valt[N],ds[N],dt[N];
int num[N][N][2],siz[N][N][2];
struct edge{
    int to,next,dis;
}e[M];
struct node{
    int id,dis;
    bool operator<(const node &x)const{
        return dis>x.dis;
    }
};
priority_queue<node>q;
struct froms{
    int id,dis;
}diss[N];
struct fromt{
    int id,dis;
}dist[N];
bool cmp3(froms x,froms y){
    return x.dis<y.dis;
}
bool cmp4(fromt x,fromt y){
    return x.dis<y.dis;
}
void add_edge(int u,int v,int c){
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=c;
    head[u]=cnt;
}
void dijkstra(int begin,int times){
    dis[times][begin]=0;
    q.push(node{begin,0});
    while(!q.empty()){
        node x=q.top();q.pop();
        for(int i=head[x.id];i;i=e[i].next){
            int y=e[i].to;
            if(dis[times][y]>x.dis+e[i].dis){
                dis[times][y]=x.dis+e[i].dis;
                q.push(node{y,dis[times][y]});
            }
        }
    }
}
signed main()
{
    memset(dis,0x3f,sizeof(dis));
    scanf("%lld%lld",&n,&m);
    scanf("%lld%lld",&s,&t);
    for(int i=1;i<=n;i++){
        scanf("%lld",&p[i]);
    }
    int u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    dijkstra(s,0);
    dijkstra(t,1);
    for(int i=1;i<=n;i++){
        diss[i]=froms{i,dis[0][i]};
        dist[i]=fromt{i,dis[1][i]};
        
    }
    sort(diss+1,diss+n+1,cmp3);
    sort(dist+1,dist+n+1,cmp4);
    int tot=1;
    vals[1]=p[diss[1].id];
    ds[s]=1;
    for(int i=2;i<=n;i++){
        if(diss[i].dis==diss[i-1].dis){
            vals[tot]+=p[diss[i].id];
            ds[diss[i].id]=tot;
        }
        else{
            tot++;
            vals[tot]+=p[diss[i].id];
            ds[diss[i].id]=tot;
        }
    }
    ns=tot;

    tot=1;
    valt[1]=p[dist[1].id];
    dt[t]=1;
    for(int i=2;i<=n;i++){
        if(dist[i].dis==dist[i-1].dis){
            valt[tot]+=p[dist[i].id];
            dt[dist[i].id]=tot;
        }
        else{
            tot++;
            valt[tot]+=p[dist[i].id];
            dt[dist[i].id]=tot;
        }
    }
    nt=tot;
    for(int i=1;i<=n;i++){
        num[ds[i]][dt[i]][0]+=p[i];
        num[ds[i]][dt[i]][1]+=p[i];
        siz[ds[i]][dt[i]][0]++;
        siz[ds[i]][dt[i]][1]++;
    }
    for(int i=0;i<=ns;i++){
        for(int j=nt;j>=0;j--){
            num[i][j][0]+=num[i][j+1][0];
            siz[i][j][0]+=siz[i][j+1][0];
        }
    }
    for(int i=0;i<=nt;i++){
        for(int j=ns;j>=0;j--){
            num[j][i][1]+=num[j+1][i][1];
            siz[j][i][1]+=siz[j+1][i][1];
        }
    }
    for(int i=ns;i>=0;i--){
        for(int j=nt;j>=0;j--){
            if(i==ns&&j==nt)continue;
            if(i!=ns){
                if(siz[i+1][j+1][0]){
                    dp[i][j][0]=max(dp[i+1][j][0],dp[i+1][j][1])+num[i+1][j+1][0];
                }
                else dp[i][j][0]=dp[i+1][j][0];
            }
            if(j!=nt){
                if(siz[i+1][j+1][1]){
                    dp[i][j][1]=min(dp[i][j+1][0],dp[i][j+1][1])-num[i+1][j+1][1];
                }
                else dp[i][j][1]=dp[i][j+1][1];
            }
        }
    }
    if(dp[0][0][0]==0)puts("Flowers");
    if(dp[0][0][0]>0)puts("Break a heart");
    if(dp[0][0][0]<0)puts("Cry");
}

I. Game on Sum (Easy Version)

标签:游戏攻略