動(dòng)態(tài)規(guī)劃是 一個(gè)重點(diǎn) 但是從來(lái)還沒(méi)有系統(tǒng)的練習(xí)過(guò)，下面HDU上的46道DP題和其狀態(tài)轉(zhuǎn)移方程，等以后練習(xí)使用
這是從百度文庫(kù)下載的 不知道原作者。。。
1.Robberies http: // acm.hdu.edu.cn/showproblem.php?pid=2955

背包;第一次做的時(shí)候把概率當(dāng)做背包(放大100000倍化為整數(shù)):在此范圍內(nèi)最多能搶多少錢 最腦殘的是把總的概率以為是搶N家銀行的概率之和… 把狀態(tài)轉(zhuǎ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]可達(dá),也就是之前過(guò);
始化為:f[0]=1,其余初始化為-1(搶0塊大洋肯定不被抓嘛)

2.最大報(bào)銷額 http: // acm.hdu.edu.cn/showproblem.php?pid=1864
又一個(gè)背包問(wèn)題,對(duì)于每張發(fā)票,要么報(bào)銷,要么不報(bào)銷,0-1背包,張數(shù)即為背包;
轉(zhuǎn)移方程:f[j]=max(f[j],f[j-1]+v[i]);
惡心地方:有這樣的輸入數(shù)據(jù)3A:100A:200A:300

3.最大連續(xù)子序列 http: // acm.hdu.edu.cn/showproblem.php?pid=1231
狀態(tài)方程: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
同上,最大連續(xù)子序列

5.Largest Rectangle http: // acm.hdu.edu.cn/showproblem.php?pid=1506
對(duì)于每一塊木板,Area=height[i]*(j-k+1) 其中,j<=x<=k,height[x]>=height[i];找j,k成為關(guān)鍵,一般方法肯定超時(shí),利用動(dòng)態(tài)規(guī)劃,如果它左邊高度大于等于它本身,那么它左邊的左邊界一定滿足這個(gè)性質(zhì),再?gòu)倪@個(gè)邊界的左邊迭代下去
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的加強(qiáng)版,把2維轉(zhuǎn)換化成以每一行底,組成的最大面積;(注意處理連續(xù)與間斷的情況);

7.Bone Collector http: // acm.hdu.edu.cn/showproblem.php?pid=2602
簡(jiǎn)單0-1背包,狀態(tài)方程:f[j]=max(f[j],f[j-v[i]]+w[i])

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

9.命運(yùn)http: // acm.hdu.edu.cn/showproblem.php?pid=2571
狀態(tài)方程: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
狀態(tài)方程: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
一維背包,逐個(gè)考慮每個(gè)物品帶來(lái)的影響,對(duì)于第i個(gè)物品: if (f[j-v[i]]==0) f[j]=0;
其中,j為逆序循環(huán),且j>=v[i]

12.數(shù)塔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.免費(fèi)餡餅http: // acm.hdu.edu.cn/showproblem.php?pid=1176
簡(jiǎn)單數(shù)塔
自底向上計(jì)算: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
簡(jiǎn)單0-1背包,題目要求的是至少收到一份Offer的最大概率,我們得到得不到的最小概率即可,狀態(tài)轉(zhuǎn)移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率,(1-f[j])為花費(fèi)j元得到Offer的最大概率

15.FATE http: // acm.hdu.edu.cn/showproblem.php?pid=2159
二維完全背包,第二層跟第三層的要順序循環(huán);(0-1背包逆序循環(huán));狀態(tài)可理解為,在背包屬性為 {m(忍耐度), s(殺怪個(gè)數(shù))} 里最多能得到的經(jīng)驗(yàn)值,之前的背包犧牲體積,這個(gè)背包犧牲忍耐度跟個(gè)數(shù)
注意: 最后掃的時(shí)候 外層循環(huán)為忍耐度,內(nèi)層循環(huán)為殺怪個(gè)數(shù),因?yàn)轭}目要求出剩余忍耐度最大,沒(méi)有約束殺怪個(gè)數(shù),一旦找到經(jīng)驗(yàn)加滿的即為最優(yōu)解;
狀態(tài)轉(zhuǎn)移方程為: f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); w[i]表示殺死第i個(gè)怪所得的經(jīng)驗(yàn)值,v[i]表示消耗的忍耐度

16.How To Type http: // acm.hdu.edu.cn/showproblem.php?pid=2577
用兩個(gè)a,b數(shù)組分別記錄Caps Lock開與關(guān)時(shí)打印第i個(gè)字母的最少操作步驟;
而對(duì)于第i個(gè)字母的大小寫還要分開討論:
Ch[i]為小寫: a[i]=min(a[i-1]+1,b[i-1]+2);不開燈直接字母,開燈則先關(guān)燈再按字母,最后保持不開燈; b[i]=min(a[i-1]+2,b[i-1]+2);不開燈則先按字母再開燈,開燈則Shift+字母(比關(guān)燈,按字母再開燈節(jié)省步數(shù)),最后保持開燈;
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]++,關(guān)燈嘛O(∩_∩)O~

17.Coins http: // acm.hdu.edu.cn/showproblem.php?pid=2844
類似于HDU1171 Big Event In HDU,一維DP,可達(dá)可不達(dá)

18.Beans http: // acm.hdu.edu.cn/showproblem.php?pid=2845
橫豎分別求一下不連續(xù)的最大子段和;
狀態(tài)方程: 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行為底,可以構(gòu)成的最大矩陣,因?yàn)樵擃}可以任意移動(dòng)列,所以只要大于等于height[i]的都可以移動(dòng)到一起,求出height>=height[i]的個(gè)數(shù)即可,這里用hash+滾動(dòng),先求出height[i]出現(xiàn)的次數(shù),然后逆序掃一遍hash[i]+=hash[i+1];

21.最少攔截系統(tǒng)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
經(jīng)典DP,最長(zhǎng)公共子序列
Len[i][j]={len[i-1][j-1]+1,(a[i]==b[j]); max(len[i-1][j],len[i][j-1])}
初始化的優(yōu)化:
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
狀態(tài)Dp[i][j]為前i件物品選j對(duì)的最優(yōu)解
當(dāng)i=j*2時(shí),只有一種選擇即 Dp[i-2][j-1]+(w[i]-w[i-1])^2
當(dāng)i>j*2時(shí),Dp[i][j]=min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)

ACM 動(dòng)態(tài)規(guī)劃題集