PAGEPAGE1動態(tài)規(guī)劃總結——經(jīng)典問題總結本文著重討論狀態(tài)是如何表示，以及方程是怎樣表示的。當然，還附上關鍵的，有可能作為模板的代碼段。但有的代碼的實現(xiàn)是優(yōu)化版的。經(jīng)典問題總結最長上升子序列（LIS）問題描述如下:設L=<a1,a2,…,an>是n個不同的實數(shù)的序列，L的遞增子序列是這樣一個子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。這里采用的是逆向思維的方法，從最后一個開始想起，即先從A[N]（A數(shù)組是存放數(shù)據(jù)的數(shù)組，下同）開始，則只有長度為1的子序列，到A[N-1]時就有兩種情況，如果a[n-1]<a[n]

則存在長度為2的不下降子序列

a[n-1],a[n]；如果a[n-1]>a[n]

則存在長度為1的不下降子序列a[n-1]或者a[n]。有了以上的思想，DP方程就呼之欲出了（這里是順序推的，不是逆序的）：DP[I]=MAX（1,DP[J]+1）

J=0,1,...,I-1但這樣的想法實現(xiàn)起來是）O(n^2)的。本題還有更好的解法，就是O(n*logn)。利用了長升子序列的性質來優(yōu)化，以下是優(yōu)化版的代碼：//最長不降子序

constintSIZE=500001;intdata[SIZE];intdp[SIZE];

//返回值是最長不降子序列的最大長度,復雜度O(N*logN)intLCS(intn){

//N是DATA數(shù)組的長度,下標從1開始

intlen(1),low,high,mid,i;

dp[1]=data[1];

for(i=1;i<=n;++i){

low=1;

high=len;

while(low<=high){

//二分

mid=(low+high)/2;

if(data[i]>dp[mid]){

low=mid+1;

}

else{

high=mid-1;

}

}

dp[low]=data[i];

if(low>len){

++len;

}

}

returnlen;}最長公共子序列（LCS）給出兩個字符串a(chǎn),b，求它們的最長、連續(xù)的公共字串。這很容易就想到以DP[I][J]表示A串匹配到I，B串匹配到J時的最大長度。則：0

I==0||J==0DP[I][J]=DP[I-1][J-1]+1

A[I]==B[J]

MAX（DP[I-1][J]，DP[I][J-1]）

不是以上情況

但這樣實現(xiàn)起來的空間復雜度為O(n^2)，而上面的方程只與第I-1行有關，所以可以用兩個一維數(shù)組來代替。以下是代碼：

//最長公共子序列constintSIZE=1001;intdp[2][SIZE];

//兩個一維數(shù)組

//輸入兩個字符串，返回最大的長度intLCS(conststring&a,conststring&b){

inti,j,flag;

memset(dp,0,sizeof(dp));

flag=1;

for(i=1;i<=a.size();++i){

for(j=1;j<=b.size();++j){

if(a[i-1]==b[j-1])

dp[flag][j]=dp[1-flag][j-1]+1;

else

dp[flag][j]=MAX(dp[flag][j-1],dp[1-flag][j]);

}

flag=1-flag;

}

returndp[1-flag][b.size()];}

01背包

有N件物品和一個容量為V的背包。第i件物品的大小是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

用DP[I][J]

表示前I件物品放入一個容量為J的背包可以獲得的最大價值。則

DP[I][J]=DP[I-1][J]

,J<C[I]MAX（DP[I-1][J]，DP[I-1][J-C[I]]+W[I]）

,J>=C[I]

這樣實現(xiàn)的空間復雜度為O(VN)，實際上可以優(yōu)化到O（V）。以下是代碼：constintMAXW=13000;

//最大重量constintMAXN=3450;

//最大物品數(shù)量

intc[MAXN];

//物品的存放要從下標1開始intw[MAXN];

//物品的存放要從下標1開始intdp[MAXW];

//不需要將背包裝滿，則將DP數(shù)組全部初始化為0//要將背包裝滿，則初始化為DP[0]=0，DP[1]…DP[V]=-1(即非法狀態(tài))intPacket(intn,intv){

inti,j;

memset(dp,0,sizeof(dp));

for(i=1;i<=n;++i){

for(j=v;j>=c[i];--j)

{

//這里是倒序，別弄錯了

dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);

}

}

returndp[v];}

完全背包問題有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

很容易可以得到這種狀態(tài)表示：用DP[I][J]

表示前I件物品放入一個容量為J的背包可以獲得的最大價值。則

DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]）

0<=K*C[I]<=J這樣的復雜度是O(V*Σ(V/c[i]))

有更好的做法，那就是利用01背包的優(yōu)化原理。在優(yōu)化的代碼中，之所以第二重循環(huán)是倒序，是為了防止重復拿，那么只要將其變?yōu)轫樞蚣纯梢灾貜腿?。代碼就不給了。

多重背包問題有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。這題仍然可以用到上一題的思想，DP表示狀態(tài)與上面的相同。方程為：DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]）不同的是K的范圍，0<=K<=N[I]&&0<=K*C[I]<=J這樣的復雜度為O(V*Σn[i])。有更好的想法就是先用二進制來劃分。將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。然后用01背包做，這樣的復雜度為O(V*Σlogn[i])。關鍵代碼：constintSIZE=1001;intdp[SIZE];intnum[SIZE],c[SIZE],w[SIZE];

//num[i]是I物品的件數(shù),C[I]是費用，W[I]是價值intMultiPack(intn,intv){

//存入?yún)?shù)，N是物品種類數(shù)，V是背包容量

inti,j,k;

memset(dp,0,sizeof(dp));

for(i=1;i<=n;++i){//存放物品的數(shù)組下標從1開始

if(c[i]*num[i]>=v){

for(j=c[i];j<=v;++j){

dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);

}

}

else{

//使用二進制劃分

k=1;

while(k<num[i]){

for(j=v;j>=k*c[i];--j){

dp[j]=MAX(dp[j],dp[j-k*c[i]]+k*w[i]);

}

num[i]-=k;

k*=2;

}

for(j=v;j>=num[i]*c[i];--j){

dp[j]=MAX(dp[j],dp[j-num[i]*c[i]]+num[i]*w[i]);

}

}

}

returndp[v];}狀態(tài)表示總結一維的狀態(tài)表示

DP的表示形式通常為：DP[I]表示取到第I個/種物品時的最優(yōu)值。DP方程的形式：DP[I]=MAX（DP[I]，DP[J]+P[I]）其中0<=J<I,P[I]表示第I個物品的屬性?；蛘逥P[I]=DP[I-1]+P[I](即只與I-1有關)

有一些題可能要將一些額外的東西也認為是物品。如HDU2059龜兔賽跑這題，需要將開始點和終點也認為是加油站，然后才以DP[I]表示到第I個加油站并加滿油的最短時間。

有一些題可以將看似二維的情況轉化為一維的情況來做。如HDU1081這題。大意是給出一個含有正數(shù)和負數(shù)的N階矩陣，求一個子矩陣使得子矩陣內(nèi)所有數(shù)的和最大。這樣的題可以將幾行合并為一行做。即枚舉就將第I行到第J行合并為一行，然后再用DP[K]=MAX（DP[K-1]，0）+ARR[K]，K是表示第K列。

有一些題是DP與暴力相結合，如POJ3267

TheCowLexicon這題。大意是給出一個長的字符串，還有若干個短的字符串，問長字符中至少要刪除幾個字符才能使得長字符串中的子字符串都與某個短字符串相對應。dp[i]表示從I到LEN-1需要刪除的最少字符串數(shù)，則dp[i]=min(dp[i+1]+1，dp[k]+del)其中dp[i+1]+1是沒有找到匹配的情況，dp[k]+del是有匹配的情況,K表示從I開始匹配,到匹配完后的最后一個字符的位置,DEL表示在匹配過程中要刪除的字符數(shù)。由于方程的特點，要從最后一個字符向第一個字符推去。中間要刪除的字符數(shù)用暴力找出。

有一些題用DP來枚舉全部的范圍，如POJ1925

Spiderman這題。用DP[I]表示到達這個位置的最小跳數(shù)。其中DP數(shù)組為dp[1000005]，這是可能跳到的全部范圍。

二維狀態(tài)表示

通常是用來處理兩種事物。DP[I][J]通常表示A的前I個和B的前J個XX的最優(yōu)值。DP方程之一：DP[I][J]=MAX（DP[I-1][J-1]+P[XX]，DP[I][J-1]+P[YY]，DP[I-1][J]+P[ZZ]）這里的XX，YY，ZZ是表示某某狀態(tài)得到的結果。DP方程之二：DP[I][J]=MAX（DP[I][J]，DP[I-1][K]+P[I][J]），其中0<=K<J，P[I][J]表示I與J的某個屬性DP方程之三：DP[I][J]=MAX（DP[I+1][J]+P[XX]，DP[I][J-1]+P[YY]）對第三種DP方程舉個例：POJ3280

CheapestPalindrome這題。大意是給出一個字符串，你可在任意位置增加或刪除字符，每增加或刪除一個字符都有一個對應的代價，求將其變?yōu)榛匚拇淖钚〈鷥r。以dp[i][j]表示從i到j要變成回文字符串的最小代價，則dp[i][j]=min{

dp[i+1][j]+{去掉X的代價}，dp[i+1][j]+{加上X的代價}，

dp[i][j-1]+{去掉Y的代價}，dp[i][j-1]+{加上Y的代價}}；算DP[I][J]時，要知道DP[I+1][J]的值，對于這類DP其實現(xiàn)方法如下所示：for(t=1;t<len;++t){

//間隔為t

for(i=1;i<len;++i){

//起始位置

if(i+t<=len){

j=i+t;

//doyourwork

}

}}有一些題看似一維，可將之變?yōu)槎S。如：POJ1159

Palindrome

這題。大意是給出一個字符，求將其變?yōu)榛匚拇尤氲淖钌僮址麛?shù)。得到字符串后，再構造一個逆串，然后求其LCS。最后將字符串長度減去LCS數(shù)就是結果。有時可以將DP與HASH相結合。如：POJ1054

TheTroublesomeFrog這題。大意是在一個坐標系中給出N個點，求找出以哪兩點作一條直線經(jīng)過的點數(shù)最多。以DP[I][J]表示過第J點和第I點的直線一共經(jīng)過的點數(shù)。DP[I][J]=（DP[J][INDEX]+1，-INF），先算出INDEX這點的坐標，然后用哈希查找，如果找到，則執(zhí)行DP[J][INDEX]+1，如果找不到則用-INF表示不存在。對于整除類型的題，如果要用DP做，那么其中有一維通常是佘數(shù)。如：POJ1745Divisibility這題，dp[i][j]表示對前I個數(shù)進行了處理,余數(shù)為J的情況帶偏移的狀態(tài)表示DP的表示形式通常為：DP[I][J]表示到第I個XX時，YY與ZZ之差為J時的最優(yōu)值。例如：POJ1837這題。題目大意：給出天平c個掛鉤的位置,然后給出g個物品的質量,將物品掛在天平上,問使天平平衡的方法有幾種。思想：用l[i]表示第i個點的x坐標值，用w[i]表示第i個砝碼的重量，用dp[i][j]表示加了i個砝碼，兩邊力矩之差為j的可能方法數(shù)，則本題只要計算出dp[i][0]，即最終力矩差為0的方法數(shù)即可。由于質量差可能為負，這里加上一個偏移量，考慮原題的數(shù)據(jù)可知，要想平衡，則一邊力矩至多為15*25*10=3750，故每個j加上3750。狀態(tài)轉移方程：dp[i+1][k+w[i]*l[j]]+=dp[i][k]，i=0~g，j=0~c，k=0~7500。輸出結果：dp[w][3750]動態(tài)規(guī)劃變態(tài)總結byzeus1：Pkuacm1163theTriangle2：Pkuacm1953WorldCupNoise//說白了就是斐波那切數(shù)列3：Pkuacm1458CommonSubsequenceLcs4：Pkuacm2250Compromise記錄路徑的lcs5：Pkuacm1159Palindrome回文串6：Pkuacm1080HummanGeneFunction7：Pkuacm2192Zipper判斷2個字符串能否組成1個字符串8：Pkuacm3356AGTC一個字符串到另一個的最小步驟9：Pkuacm1887TestingtheCATCHER最長下降子序列10：Pkuacm2533LongestOrderedSubsequence最長上升子序列11：Pkuacm1631Bridgingsignals最長上升子序列的加強版….二分法12：Pkuacm1157LITTLESHOPOFFLOWERS13：Pkuacm1088滑雪14：Pku1050TotheMax15：Pku1050TotheMax最大線段和的加強板…..二維的16：Pku1014dividing17:Pkuacm1160postoffice18:pkuacm1015JuryCompromise19:hdoj2546飯卡20:pku1837Balance21:pku3267TheCowLexicon22:Pku1742Coins//走塔經(jīng)典的dp#include"iostream"usingnamespacestd;intmax(inta,intb){returna>b?a:b;}intmain(){intn,i,j;inta[100][100];intf[100];while(scanf("%d",&n)>0){for(i=0;i<n;i++)for(j=0;j<=i;j++){scanf("%d",&a[i][j]);if(i==n-1)f[j]=a[i][j];}for(i=n-2;i>=0;i--){for(j=0;j<=n-1;j++)if(f[j]>f[j+1])f[j]=f[j]+a[i][j];elsef[j]=f[j+1]+a[i][j];}printf("%d\n",f[0]);}system("pause");}2：Pkuacm1953WorldCupNoise//說白了就是斐波那切數(shù)列#include"iostream"usingnamespacestd;intmain(){intn,m;inti;intf[100];f[0]=2;f[1]=3;scanf("%d",&n);for(i=2;i<100;i++){f[i]=f[i-1]+f[i-2];}for(i=0;i<n;i++){ scanf("%d",&m);{printf("Scenario#%d:\n%d\n\n",i+1,f[m-1]);}}}3：Pkuacm1458CommonSubsequenceLcs經(jīng)典#include"iostream"#include"cstring"usingnamespacestd;intsetmax(inta,intb){if(a>b)returna;elsereturnb;}intf[8100][8100];main(){chars1[800];chars2[800];inti,j;intsl1,sl2;while(scanf("%s%s",&s1,&s2)!=EOF){sl1=strlen(s1);sl2=strlen(s2);for(i=0;i<sl1;i++){f[0][i]=0;f[i][0]=0;}for(i=1;i<sl1+1;i++)for(j=1;j<sl2+1;j++){if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1]+1;elsef[i][j]=setmax(f[i-1][j],f[i][j-1]);}printf("%d\n",f[i-1][j-1]);}}4：Pkuacm2250Compromise記錄路徑的lcs#include"iostream"#include"string"usingnamespacestd;#defineN100structnode{strings;}s1[N],s2[N];intf[N][N];intpath[N][N];stringtemp;intflag;voidlcs(inti,intj){if(i==0||j==0)return;if(path[i][j]==1){lcs(i-1,j-1);{if(flag!=1){cout<<s1[i-1].s<<endl;flag=1;}elsecout<<s1[i-1].s<<"";}}elseif(path[i][j]==2)lcs(i-1,j);elselcs(i,j-1);}intmain(){inti=0,j;intlen1,len2;while(cin>>s1[0].s){memset(f,0,sizeof(f));i=1;while(1){ cin>>temp; if(temp=="#")break; s1[i++].s=temp;}len1=i;i=0;while(1){cin>>temp;if(temp=="#")break;s2[i++].s=temp;}len2=i;memset(path,0,sizeof(path));for(i=0;i<=len1;i++)for(j=0;j<=len2;j++)if(i==j)f[i][j]=1;for(i=1;i<=len1;i++)for(j=1;j<=len2;j++){if(s1[i-1].s==s2[j-1].s){f[i][j]=f[i-1][j-1]+1;path[i][j]=1;}elseif(f[i-1][j]>=f[i][j-1]){f[i][j]=f[i-1][j];path[i][j]=2;}else{f[i][j]=f[i][j-1];path[i][j]=3;}}flag=1;lcs(len1,len2);cout<<endl;}}5：Pkuacm1159Palindrome回文串帶有些許優(yōu)化的lcs#include"iostream"#include"string"#include"algorithm"usingnamespacestd;inta[5005],b[5005];intc[3],d[3];strings1,s2;intmain(){intm,n=0;inti,j;while(cin>>n){if(n==0)break;cin>>s1;s2=s1;reverse(s2.begin(),s2.end());memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=0;i<n;i++){b[0]=0;for(j=0;j<n;j++){if(s1[i]==s2[j]){ b[j+1]=a[j]+1;}elseif(b[j]>a[j+1]){b[j+1]=b[j];}elseif(b[j]<a[j+1]){b[j+1]=a[j+1];}}for(j=0;j<=n;j++)a[j]=b[j];}printf("%d\n",n-b[n]);}}6：Pkuacm1080HummanGeneFunction#include"iostream"usingnamespacestd;intf[250][250];intg[250][250];chars1[180];chars2[180];intmaxnum(intx,inty,intz){intzz=x>y?x:y;returnzz>z?zz:z;}voidmake(){f[1][1]=5;f[1][2]=-1;f[1][3]=-2;f[1][4]=-1;f[1][5]=-3;f[2][1]=-1;f[2][2]=5;f[2][3]=-3;f[2][4]=-2;f[2][5]=-4;f[3][1]=-2;f[3][2]=-3;f[3][3]=5;f[3][4]=-2;f[3][5]=-2;f[4][1]=-1;f[4][2]=-2;f[4][3]=-2;f[4][4]=5;f[4][5]=-1;f[5][1]=-3;f[5][2]=-4;f[5][3]=-2;f[5][4]=-1;f[5][5]=-99999;}intsw(charch){if(ch=='A')return1;elseif(ch=='C')return2;elseif(ch=='G')return3;elseif(ch=='T')return4;elseif(ch=='-')return5;}intfind(charch1,charch2){returnf[sw(ch1)][sw(ch2)];}intmain(){make();intsl1,sl2,i,j,m;memset(g,0,sizeof(0));cin>>m;while(m--){cin>>sl1;cin>>s1;cin>>sl2;cin>>s2;for(i=1;i<=sl2;i++)g[0][i]=g[0][i-1]+find('-',s2[i-1]);for(i=1;i<=sl1;i++)g[i][0]=g[i-1][0]+find(s1[i-1],'-');for(i=1;i<=sl1;i++)for(j=1;j<=sl2;j++){g[i][j]=maxnum(g[i][j-1]+find('-',s2[j-1]),g[i-1][j]+find(s1[i-1],'-'),g[i-1][j-1]+find(s1[i-1],s2[j-1]));}cout<<g[sl1][sl2]<<endl;}}7：Pkuacm2192Zipper判斷2個字符串能否組成1個字符串//用動態(tài)規(guī)劃解決，ok[i][j]表示str1長度為i的前綴和str2長度為j的后綴能否組成目標中str中長度為i+j的前綴串#include"iostream"usingnamespacestd;inti,j,n;intsl1,sl2,sl3;chars1[500],s2[500],s3[500];intf[500][500];intmain(){intcount=0;scanf("%d",&n);while(n--){count++;memset(f,0,sizeof(f));scanf("%s%s%s",s1,s2,s3);sl1=strlen(s1);sl2=strlen(s2);sl3=strlen(s3);for(j=0;j<strlen(s1);j++){if(s1[j]==s3[j])f[j+1][0]=1;elsebreak;}for(i=0;i<strlen(s2);i++){if(s2[i]==s3[i])f[0][i+1]=1;elsebreak;}for(i=0;i<=sl1;i++)for(j=0;j<=sl2;j++){if(!(i==0&&j==0))if(s1[i]==s3[i+j]&&f[i][j]==1)f[i+1][j]=1;if(s2[j]==s3[i+j]&&f[i][j]==1)f[i][j+1]=1;}printf("Dataset%d:",count);if(f[sl1][sl2]==1)printf("yes\n");elseprintf("no\n");}}8：Pkuacm3356AGTC一個字符串到另一個的最小步驟#include"iostream"#include"string"usingnamespacestd;intsetmin(intx,inty,intz){intxx=x>y?y:x;returnxx>z?z:xx;}strings1,s2;intf[1005][1005];intmain(){intn,m;inti,j;while(cin>>n){cin>>s1;cin>>m;cin>>s2;for(i=0;i<=n;i++)f[i][0]=i;for(i=0;i<=m;i++)f[0][i]=i;for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(s1[i-1]==s2[j-1])f[i][j]=setmin(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]);elsef[i][j]=setmin(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1);}cout<<f[n][m]<<endl;}}9：Pkuacm1887TestingtheCATCHER最長下降子序列#include"iostream"usingnamespacestd;inta[32769],f[32769];intmain(){inti,j,n,max;intcount=0;while(1){count++;scanf("%d",&a[0]);if(a[0]==-1)break;i=1;while(1){scanf("%d",&a[i]);if(a[i]==-1)break;i++;}n=i;max=0;memset(f,0,sizeof(f));for(i=1;i<=n;i++){f[i]=1;for(j=0;j<=i;j++){if(a[j-1]>a[i-1]&&f[j]+1>f[i])f[i]=f[j]+1;if(f[i]>max)max=f[i];}}printf("Test#%d:\n",count);printf("maximumpossibleinterceptions:%d\n\n",max);}}10：Pkuacm2533LongestOrderedSubsequence最長上升子序列#include"iostream"usingnamespacestd;intf[10000];inta[10000];intmain(){intn,i,j,max;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){scanf("%d",&a[i]);}memset(f,0,sizeof(f));max=0;for(i=1;i<=n;i++){f[i]=1;for(j=0;j<=i;j++)if(a[j-1]<a[i-1]&&f[j]+1>f[i])f[i]=f[j]+1;if(f[i]>max)max=f[i];}printf("%d\n",max);}}11：Pkuacm1631Bridgingsignals最長上升子序列的加強版….二分法#include"iostream"#include"string"usingnamespacestd;#defineN50000intf[N];inta[N];intmain(){intn,m,i,j,max;scanf("%d",&n);while(n--){max=-99;memset(f,0,sizeof(f));scanf("%d",&m);for(i=0;i<m;i++){scanf("%d",&a[i]);//f[i]=a[i];}f[1]=a[0];ints=1;intl,r,mid;for(i=1;i<m;i++){if(f[s]<a[i])f[++s]=a[i];else{l=0;r=s;mid=(l+r)>>1;while(l<=r){mid=(l+r)>>1;f[mid]<a[i]?l=mid+1:r=mid-1;}f[l]=a[i];}}printf("%d\n",s);}}12：Pkuacm1157LITTLESHOPOFFLOWERS該題也是經(jīng)典的動態(tài)規(guī)劃，題目敘述的依然很麻煩，其實簡化一下就是這樣的：例如下面這個例子就是：3表示行，5表示列，然后在下面的3行5列每一行選一個數(shù)，使這3個數(shù)最大，要求選的數(shù)列數(shù)必須依次增大，就是從左上方想右下方選3個數(shù)使和最大。35723-5-2416521-41023-215-4-2020#include"iostream"usingnamespacestd;#defineN5000intf[N][N];intw[N][N];intmain(){intn,m,i,j,k;while(cin>>n>>m){for(i=0;i<n;i++)for(j=0;j<m;j++)cin>>w[i][j];for(i=0;i<n;i++)for(j=0;j<m;j++)f[i][j]=-50000;for(i=1;i<m;i++)f[1][i]=w[0][i-1];for(i=2;i<=n;i++){for(j=1;j<=m;j++){if(j>=i)for(k=1;k<j;k++)if(f[i][j]<f[i-1][k]+w[i-1][j-1])f[i][j]=f[i-1][k]+w[i-1][j-1];}}intmax=-50000;for(i=0;i<=m;i++)if(f[n][i]>max)max=f[n][i];printf("%d\n",max);}}13：Pkuacm1088滑雪12345161718196152425207142322218131211109一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。輸出最長區(qū)域的長度。#include"iostream"usingnamespacestd;inth[100][100];intf[100][100];intdir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};intr,c;booljudge(intx,inty){if(x>=0&&y>=0&&x<r&&y<c)returntrue;elsereturnfalse;}intdp(inti,intj){intmax=0,xi,yi,k;if(f[i][j]!=0)returnf[i][j];for(k=0;k<4;k++){xi=i+dir[k][0];yi=j+dir[k][1];if(judge(xi,yi)&&h[i][j]>h[xi][yi]){intnum=dp(xi,yi);if(num>max)max=num;}}f[i][j]=max+1;returnmax+1;}intmain(){inti,j;inttemp,max;while(cin>>r>>c){for(i=0;i<r;i++)for(j=0;j<c;j++){cin>>h[i][j];}memset(f,0,sizeof(f));max=0;for(i=0;i<r;i++){for(j=0;j<c;j++){temp=dp(i,j);max=max>temp?max:temp;}}cout<<max<<endl;}}14：hdoj1003maxnum#include"iostream"usingnamespacestd;intf[100005];inta[100005];intmain(){intnum,n,i,j;intst,end,now,max;intflag;intcount=0;intk;cin>>num;while(num--){count++;cin>>n;for(i=0;i<n;i++)cin>>a[i];now=0;max=-999;k=1;for(i=0;i<n;i++){now+=a[i];if(now>max){max=now;end=i+1;st=k;}if(now<0){now=0;k=i+2;}}printf("Case%d:\n",count);printf("%d%d%d\n",max,st,end);if(num!=0)printf("\n");}return0;}15：Pku1050TotheMax最大線段和的加強板…..二維的#include"iostream"usingnamespacestd;intn,i,j,cnt,now,maxx,k;inta[150][150];ints[150][150][150];intmain(){while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%d",&a[i][j]);s[i][i][j]=a[i][j];}for(i=1;i<n;i++)for(j=i+1;j<=n;j++)for(k=1;k<=n;k++){s[i][j][k]=s[i][j-1][k]+a[j][k];}maxx=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++){cnt=0;now=0;for(k=1;k<=n;k++){cnt+=s[i][j][k];if(cnt>now)now=cnt;if(cnt<0)cnt=0;}if(now>maxx)maxx=now;}printf("%d\n",maxx);}return0;}16：Pku1014dividing實在不會做先抄個代碼#include<stdio.h>boolopt[60000];intnum=0;intmid,max;intstone[7];intinput(){scanf("%d%d%d%d%d%d",&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]);if(!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]){return1;}//讀到末行num++;printf("Collection#%d:\n",num);mid=0;for(inti=1;i<=6;i++)mid+=stone[i]*i;if(mid%2==1)//明顯的剪枝{printf("Can'tbedivided.\n\n");return2;}elsemid/=2;//我們的任務就是求optreturn0;}voiddp(){memset(opt,0,60000);//初始化，opt所有成員為falseopt[0]=true;//opt[0]顯然是truemax=0;//當前最大值是0for(inti=1;i<=6;i++){if(stone[i]>0){for(intj=max;j>=0;j--)//從當前最大值開始往下算if(opt[j])//找到可行的j{if(opt[mid])//判斷是否已經(jīng)求出結果{printf("Canbedivided.\n\n");return;}for(intk=1;k<=stone[i];k++)//在剛找到的可行j基礎上加石頭.{if(j+k*i>mid||opt[j+k*i])break;//如果已經(jīng)大于總價值的一半mid，或opt[j+k*i]已計算，跳出循環(huán)opt[j+k*i]=true;}}}max=max+i*stone[i];//更新當前最大值if(max>mid)max=mid;//如果當前最大值超過了mid，對其賦值為mid}printf("Can'tbedivided.\n\n");//如果從1到6循環(huán)完一遍后仍然沒有算出opt[mid]，說明無解}intmain(){while(1){intt=input();switch(t){case1:return0;//讀到末行，結束case2:continue;//讀到明顯的剪枝default:dp();}}return0;}17:Pkuacm1160postoffice貼代碼題目給出m個村莊及其距離，給出n個郵局，要求怎么建n個郵局使代價最小。思路：用opt[i][j]記錄把前i個郵局建到前j個村莊中的最優(yōu)解，用cost[i][j]記錄所有在i到j村莊中，建1個郵局的最小代價。顯然郵局應該設到中點。讓前i個郵局覆蓋前j個村莊，第i+1個郵局覆蓋第j+1至j+k個村莊(j+k<=n)，則狀態(tài)轉移方程為w[i+1][j+k]=min{w[i][j]+cost[j+1][j+k];}(k+j<=n)Cost數(shù)組存放從i到j中有一個郵局的最小代價，顯然該郵局應該放在中間W[i][j]表示前i個郵局覆蓋前j個村莊的最小代價，對于i=1來說，w[i][j]=cost[i][j],讓前2個郵局覆蓋前j個村莊，也就是i=2的情況，可能是一下情況的最優(yōu)解：第一個郵局覆蓋第一個村莊，第二個村莊覆蓋2-j個村莊，或者第一個郵局覆蓋第1-2個村莊，第二個村莊覆蓋3-j個村莊，第一個郵局覆蓋第1-3個村莊，第二個村莊覆蓋4-j個村莊，等等等等#include"iostream"usingnamespacestd;intcost[310][310];intw[310][310];#definemax3000000intmain(){inti,j,k,m,n,mid,q,v[310];while(scanf("%d%d",&m,&n)!=EOF){for(i=1;i<=m;i++)scanf("%d",&v[i]);memset(cost,0,sizeof(cost));for(i=1;i<=m;i++)for(j=i;j<=m;j++){mid=(i+j)/2;for(k=i;k<=mid;k++)cost[i][j]=cost[i][j]+v[mid]-v[k];for(k=mid+1;k<=j;k++)cost[i][j]=cost[i][j]+v[k]-v[mid];}for(i=0;i<=n;i++)for(j=0;j<=m;j++)w[i][j]=max;w[0][0]=0;for(i=0;i<=n;i++)for(j=0;j<=m;j++)if(w[i][j]<max){for(k=1;k<=m-j;k++){q=w[i][j]+cost[j+1][j+k];if(w[i+1][j+k]>q)w[i+1][j+k]=q;}}printf("%d\n",w[n][m]);}return0;}18:pkuacm1015JuryCompromise題目大意：在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選n個人作為陪審團的候選人，然后再從這n個人中選m人組成陪審團。選m人的辦法是：控方和辯方會根據(jù)對候選人的喜歡程度，給所有候選人打分，分值從0到20。為了公平起見，法官選出陪審團的原則是：選出的m個人，必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同，那么選辯控雙方總分之和最大的方案即可。分析：顯然本題如不用DP的話，顯然會超時。我們將第i個人的辯方和控方的差記錄在sub[i]中，將第i個人的辯方和控方的和記錄在plus[i]中，現(xiàn)在用f(j,k)表示取j個侯選人中，辯控和最大的那個方案。如果沒法選j個人使其控辯差為k的話，令f(j,k)=-1;本題的要求選出m個人，即最終解為f(m,k)，(-21*m<=k<=21*m)其中k的絕對值最小且有解。顯然f(j,k)是某個可行方案f(j-1,x)(-21*m<=x<=21*m)演變而來。可行方案f(j-1,x)演變成f(j,k)的條件是:存在某個侯選人i，它在方案f(j-1,x)中沒有被選上，且x+sub[i]=k,并且在所有滿足上述條件的方案中，f(j-1,x)+plus[i]最大。此時f(j-1,x)+plus[i]=f(j,k)。在上述推導中，另一個難點是如何標記i是不是已經(jīng)在方案f(j-1,x)中。此時，我們可以用一個path(j,k)來記錄相應的f(j,k)中最后選的人。例如上面的,則path(j,k)=i;倒數(shù)第二個人選的編號為path(j-1,k-sub[i]),依次類推，我們就能求出某個方案中所有人的編號。實際解題中，則于控辯差有可能為負，由于控辯差的范圍為[-21*m,21*m]我們可將所有控辯差加上m*21來解決，保證其值為正。#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;intm,n;intf[21][850];intpath[21][850];intPLUS[500],sub[500],ans[21],la,size;intmain(){inti,ii,jj,j,k,a,b,test=1;while(cin>>n>>m&&n+m){size=21*m;for(i=1;i<=n;i++){cin>>a>>b;PLUS[i]=a+b;sub[i]=a-b;}memset(f,-1,sizeof(f));memset(path,-1,sizeof(path));f[0][size]=0;path[0][size]=0;for(i=1;i<=n;i++)//先算出第1個人的編號{if(f[1][size+sub[i]]<PLUS[i]){path[1][size+sub[i]]=i;f[1][size+sub[i]]=PLUS[i];}}for(i=1;i<m;i++){for(j=0;j<2*size;j++){if(path[i][j]>=0){for(k=1;k<=n;k++){if(f[i+1][j+sub[k]]<f[i][j]+PLUS[k]){for(jj=i,ii=j;jj>=1;jj--)//順藤摸瓜.判斷第k個人有沒有出現(xiàn)過{if(path[jj][ii]==k)break;ii-=sub[path[jj][ii]];}if(jj<1){path[i+1][j+sub[k]]=k;f[i+1][j+sub[k]]=f[i][j]+PLUS[k];}}}}}}for(j=0;j<=2*size;j++)//取絕對值最小的作為最優(yōu)解{if(f[m][size+j]>=0||f[m][size-j]>=0){if(f[m][size+j]>f[m][size-j])i=size+j;elsei=size-j;break;}}cout<<"Jury#"<<test++<<endl;cout<<"Bestjuryhasvalue"<<(f[m][i]+i-size)/2<<"forprosecutionandvalue"<<(f[m][i]-i+size)/2<<"fordefence:"<<endl;la=0;for(j=m,k=i;j>=1;j--){ans[la++]=path[j][k];k-=sub[ans[la-1]];}sort(ans,ans+la);//排序輸出for(i=0;i<la;i++)cout<<""<<ans[i];cout<<endl;}