转移方程练习

hwx12233 · 2020-07-31 08:19:29 · 个人记录

P5007 DDOSvoid 的疑惑

塔：不能重复选dp

这里提供一种dp思路

不要去记载两者是多少

而去记录的差值

如dp[i][j]

$j$表示差为j 整个存的是你想求的东西 ```cpp int n,a[100],f[2][N]; int main(){ n=read(); memset(f,128,sizeof(f)); for(int i=1;i<=n;i++)a[i]=read(); f[0][500000]=0; int ans=0; for(int i=1;i<=n;i++) for(int j=0;j<=1000000;j++){ f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j]); if(j-a[i]>=0)f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j-a[i]]+a[i]); if(j+a[i]<=1000000)f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j+a[i]]); if(j==500000)ans=max(ans,f[(i%2)][j]); } cout<<(ans==0?-1:ans); } ``` # CF213C Relay Race [CF213C Relay Race](https://www.luogu.com.cn/problem/CF213C) 看到题目有一个很朴素的算法 $dp[i][j][k][z]$表示一个在$i,j$一个在$k,z$的最大值同时按照步数向下转移但是发现时间空间都会爆炸在看完题解后我们有一个惊奇的发现只要统计步数和在哪行就可以知道在哪列了因此我们状态设计为$dp[i][j][z]$表示走了$i$步一个点在j行另一个在$z$行的最大收益转移时判一下有没有走出去就好了当$j=z$时说明两者经过同一点只算一遍就好了 ```cpp int n,a[400][400],f[607][310][310]; memset(f,128,sizeof(f)); f[1][1][1]=a[1][1]; for(int i=2;i<=n+n-1;i++) for(int j=1;j<=n;j++)if(i-j+1>=1&&i-j+1<=n) for(int k=1;k<=n;k++)if(i-k+1>=1&&i-k+1<=n){ int tmp; if(j!=k)tmp=a[j][i-j+1]+a[k][i-k+1]; else tmp=a[j][i-j+1]; f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+tmp); f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]+tmp); f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+tmp); f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+tmp); } cout<<f[n+n-1][n][n]; ``` # 任务安排 [任务安排](https://www.luogu.com.cn/problem/P2365) ### 后面的贡献前面来算可以想到$f[i][j]$表示到第$i$个任务分了j次 ```cpp f[i][j]=min(f[k][j-1]+(s*j+sumt[i])*(sumf[i]-sumf[k])) ``` 但是可以这样想我们不用知道分了几次我们只要知道到这个点之前最小的值就好了如果算每一次时给后面加入$s*(pref_n-pref_j)

那就不用枚举j了

f[i]=min(f[i],f[j]+pret[i]*(pref[i]-pref[j])+s*(pref[n]-pref[j]));

采集资源

像这种买的东西会对后面产生后效的

我们可以先预处理出花k块钱能产生的最大生产量

再用递推

for(int i=1;i<=n;i++)
for(int j=1;j<=t;j++)if(j>=a[i])f[j]=max(f[j],f[j-a[i]]+b[i]);

for(int i=0;i<=2000;i++){
    if(dp[i][t]>0)return printf("%d",i),0;
    for(int j=0;j<=t;j++){
        if(dp[i][j]<0)continue;
        for(int k=0;k<=j;k++){
            if(f[k]<0)continue;
            if(j-k+f[k]+dp[i][j]>=t)return printf("%d",i+1),0;
            dp[i+1][j-k+f[k]+dp[i][j]]=max(dp[i+1][j-k+f[k]+dp[i][j]],dp[i][j]+f[k]);
            }
        }
    }

区间dp

CF1107E Vasya and Binary String

提供一种dp思路

那么就有两个转移式子 ``` dp[i][j][k]=dp[i+1][j][0]+a[k+1] dp[i][j][k]=max(dp[i+1][z-1][0]+dp[z][j][k+1])(i+1<=z<=j)) ``` [CF149D Coloring Brackets](https://www.luogu.com.cn/problem/CF149D) 本题若设出$dp[i][j][0/1/2][0/1/2]$未免太过繁琐观察到这道题中$[1][0], [2][0], [0][1], [0][2]$相同 $[1][1], [1][2], [2][1], [2][2]$相同故我们可以想到用三个状态表示 ```` [0]表示都不涂 [1]表示涂一边 [2]表示涂两边 ```` 最重要的是转移时要看准一种状态推比如[1,1] 由$\ $左[1,0]$\times$右([0,1]+[1,1]+[2,1]) 或左([1,1]\ [1,2])$\times$右([2,1]\ [1,2]+[0,1]\ [0,1]) 如此推出 # DP [RT](https://www.luogu.com.cn/problem/CF1579G) 有时我们想设$dp[i][j][k]

表示第i个时左端点为j现在在k时区间的最小长度

但我们可以优化

答案即为$dp[n][0 - top]+(0-top)

for(int i=1;i<=n;i++){
            for(int j=0;j<=top;j++){
                chmin(dp[i][j],dp[i-1][j+a[i]]+a[i]);
                if(j>=a[i])chmin(dp[i][j],max(dp[i-1][j-a[i]]-a[i],0));
            }
        }