ACM 动态规划题集

动态规划是 一个重点 但是从来还没有系统的练习过，下面HDU上的46道DP题和其状态转移方程，等以后练习使用
这是从百度文库下载的 不知道原作者。。。
1.Robberies http: // acm.hdu.edu.cn/showproblem.php?pid=2955

背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=max{f[j],f[j-q[i].v]+q[i].money}(f[j]表示在概率j之下能抢的大洋);
正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v) 其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前过;
始化为:f[0]=1,其余初始化为-1(抢0块大洋肯定不被抓嘛)

2.最大报销额 http: // acm.hdu.edu.cn/showproblem.php?pid=1864
又一个背包问题,对于每张发票,要么报销,要么不报销,0-1背包,张数即为背包;
转移方程:f[j]=max(f[j],f[j-1]+v[i]);
恶心地方:有这样的输入数据3A:100A:200A:300

3.最大连续子序列 http: // acm.hdu.edu.cn/showproblem.php?pid=1231
状态方程:sum[i]=max(sum[i-1]+a[i],a[i]);最后从头到尾扫一边
也可以写成:
Max=a[0];
Current=0;
for (i=0;i<n;i++)
{
if (Current<0)
Current=a[i];
else
Current+=a[i];
if (Current>Max)
Max=Current;
}

4.max sum http: // acm.hdu.edu.cn/showproblem.php?pid=1003
同上,最大连续子序列

5.Largest Rectangle http: // acm.hdu.edu.cn/showproblem.php?pid=1506
对于每一块木板,Area=height[i]*(j-k+1) 其中,j<=x<=k,height[x]>=height[i];找j,k成为关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去
for (i=1;i<=n;i++)
{
while (a[l[i]-1]>=a[i])
l[i]=l[l[i]-1];

}

for (i=n;i>=1;i--)
{
while (a[r[i]+1]>=a[i])
r[i]=r[r[i]+1];
}

6.City Game http: // acm.hdu.edu.cn/showproblem.php?pid=1505
1506的加强版,把2维转换化成以每一行底,组成的最大面积;(注意处理连续与间断的情况);

7.Bone Collector http: // acm.hdu.edu.cn/showproblem.php?pid=2602
简单0-1背包,状态方程:f[j]=max(f[j],f[j-v[i]]+w[i])

8.Super Jumping http: // acm.hdu.edu.cn/showproblem.php?pid=1087
最大递增子段和,状态方程:sum[j]=max{sum[i]}+a[j]; 其中,0<=i<=j,a[i]<a[j]

9.命运http: // acm.hdu.edu.cn/showproblem.php?pid=2571
状态方程:sum[i][j]=max{sum[i-1][j],sum[i][k]}+v[i][j];其中1<=k<=j-1,且k是j的因子

10.Monkey And Banana http: // acm.hdu.edu.cn/showproblem.php?pid=1069
状态方程:f[j]=max{f[i]}+v[j];其中,0<=i<=j,w[i]<w[j],h[i]<h[j]

11.Big Event in HDU http: // acm.hdu.edu.cn/showproblem.php?pid=1171
一维背包,逐个考虑每个物品带来的影响,对于第i个物品: if (f[j-v[i]]==0) f[j]=0;
其中,j为逆序循环,且j>=v[i]

12.数塔http: // acm.hdu.edu.cn/showproblem.php?pid=2084
自底向上:dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+v[i][j];

13.免费馅饼http: // acm.hdu.edu.cn/showproblem.php?pid=1176
简单数塔
自底向上计算:dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+v[i][j];处理边界

14.I Need A Offer http: // acm.hdu.edu.cn/showproblem.php?pid=1203
简单0-1背包,题目要求的是至少收到一份Offer的最大概率,我们得到得不到的最小概率即可,状态转移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率,(1-f[j])为花费j元得到Offer的最大概率

15.FATE http: // acm.hdu.edu.cn/showproblem.php?pid=2159
二维完全背包,第二层跟第三层的要顺序循环;(0-1背包逆序循环);状态可理解为,在背包属性为 {m(忍耐度), s(杀怪个数)} 里最多能得到的经验值,之前的背包牺牲体积,这个背包牺牲忍耐度跟个数
注意: 最后扫的时候 外层循环为忍耐度,内层循环为杀怪个数,因为题目要求出剩余忍耐度最大,没有约束杀怪个数,一旦找到经验加满的即为最优解;
状态转移方程为: f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); w[i]表示杀死第i个怪所得的经验值,v[i]表示消耗的忍耐度

16.How To Type http: // acm.hdu.edu.cn/showproblem.php?pid=2577
用两个a,b数组分别记录Caps Lock开与关时打印第i个字母的最少操作步骤;
而对于第i个字母的大小写还要分开讨论:
Ch[i]为小写: a[i]=min(a[i-1]+1,b[i-1]+2);不开灯直接字母,开灯则先关灯再按字母,最后保持不开灯; b[i]=min(a[i-1]+2,b[i-1]+2);不开灯则先按字母再开灯,开灯则Shift+字母(比关灯,按字母再开灯节省步数),最后保持开灯;
Ch[i]为大写: a[i]=min(a[i-1]+2,b[i-1]+2); b[i]=min(a[i-1]+2,b[i-1]+1)
最后,b[len-1]++,关灯嘛O(∩_∩)O~

17.Coins http: // acm.hdu.edu.cn/showproblem.php?pid=2844
类似于HDU1171 Big Event In HDU,一维DP,可达可不达

18.Beans http: // acm.hdu.edu.cn/showproblem.php?pid=2845
横竖分别求一下不连续的最大子段和;
状态方程: Sum[i]=max(sum[j])+a[i];其中,0<=j<i-1;

19.Largest Submatrix http: // acm.hdu.edu.cn/showproblem.php?pid=2870
枚举a,b,c 最大完全子矩阵,类似于HDU15051506

20.Matrix Swapping II http: // acm.hdu.edu.cn/showproblem.php?pid=2830
最大完全子矩阵,以第i行为底,可以构成的最大矩阵,因为该题可以任意移动列,所以只要大于等于height[i]的都可以移动到一起,求出height>=height[i]的个数即可,这里用hash+滚动,先求出height[i]出现的次数,然后逆序扫一遍hash[i]+=hash[i+1];

21.最少拦截系统http: // acm.hdu.edu.cn/showproblem.php?pid=1257
两种做法,一是贪心,从后往前贪;二是DP;
if (v[i]>max{dp[j]}) (0<=j<len)
dp[len++]=v[i];

22.Common Subsequence http: // acm.hdu.edu.cn/showproblem.php?pid=1159
经典DP,最长公共子序列
Len[i][j]={len[i-1][j-1]+1,(a[i]==b[j]); max(len[i-1][j],len[i][j-1])}
初始化的优化:
for (i=0;i<a;i++)
for (j=0;j<b;j++)
len[i][j]=0;
for (i=1;i<=a;i++)
for (j=1;j<=b;j++)
if (ch1[i-1]==ch2[j-1])
len[i][j]=len[i-1][j-1]+1;
else
len[i][j]=max(len[i-1][j],len[i][j-1]);

23.搬寝室http: // acm.hdu.edu.cn/showproblem.php?pid=1421
状态Dp[i][j]为前i件物品选j对的最优解
当i=j*2时,只有一种选择即 Dp[i-2][j-1]+(w[i]-w[i-1])^2
当i>j*2时,Dp[i][j]=min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)

ACM 动态规划题集