動态規劃總結——經典問題總結

本文着重讨論狀态是如何表示，以及方程是怎樣表示的。當然，還附上關鍵的，有可能作為模闆的代碼段。但有的代碼的實作是優化版的。

經典問題總結

最長上升子序列（LIS）

最長上升子序列問題是各類資訊學競賽中的常見題型，也常常用來做介紹動态規劃算法的引例，筆者接下來将會對POJ上出現過的這類題目做一個總結，并介紹解決LIS問題的兩個常用

算法(n^2)和(nlogn).

問題描述:給出一個序列a1,a2,a3,a4,a5,a6,a7....an,求它的一個子序列（設為s1,s2,...sn），使得這個子序列滿足這樣的性質，s1<s2<s3<...<sn并且這個子序列的長度最長。輸出這個最長的長度。（為了簡化該類問題，我們将諸如最長下降子序列及最長不上升子序列等問題都看成同一個問題，其實仔細思考就會發現，這其實隻是<符号定義上的問題，并不影響問題的實質）

例如有一個序列:1 7 3 5 9 4 8,它的最長上升子序列就是 1 3 4 8 長度為4.

算法1(n^2):我們依次周遊整個序列，每一次求出從第一個數到目前這個數的最長上升子序列，直至周遊到最後一個數字為止，然後再取dp數組裡最大的那個即為整個序列的最長上升子序列。我們用dp[i]來存放序列1-i的最長上升子序列的長度，那麼dp[i]=max(dp[j])+1,(j∈[1, i-1]); 顯然dp[1]=1,我們從i=2開始周遊後面的元素即可。

下面是模闆：

//最長上升子序列(n^2)模闆

//入口參數：1.數組名稱 2.數組長度（注意從1号位置開始）

template<class T>

int LIS(T a[],int n)

{

int i,j;

int ans=1;

int m=0;

int *dp=new int[n+1];

dp[1]=1; //dp[i]都初始化為1；

for(i=2;i<=n;i++) //j依次由j=0，到

i-1，每次循環都看dp[j]是否大于m，，大于的話計算出dp[i]的值，，ans記錄dp[i]的最大值

{

m=0;

for(j=1;j<i;j++)

{

if(dp[j]>m&&a[j]<a[i])

m=dp[j];

}

dp[i]=m+1;

if(dp[i]>ans)

ans=dp[i];

}

return ans;

}

問題描述如下:

設L=<a1,a2,…,an>是n個不同的實數的序列，L的遞增子序列是這樣一個子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

這裡采用的是逆向思維的方法，從最後一個開始想起，即先從A[N]（A數組是存放資料的數組，下同）開始，則隻有長度為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

但這樣的想法實作起來是）O(n^2)的。本題還有更好的解法，就是O(n*logn)。利用了長升子序列的性質來優化，以下是優化版的代碼：

//最長不降子序

const int SIZE=500001;

int data[SIZE];

int dp[SIZE];

//傳回值是最長不降子序列的最大長度,複雜度O(N*logN)

int LCS(int n){ //N是DATA數組的長度,下标從1開始

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

dp[1]=data[1];

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

low=1;

high=len;

while( low<=high ) { //二分

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

mid=(low+high)/2; {

low=mid+1;

}

else {

high=mid-1;

}

dp[low]=data[i];

if( low>len ) {

++len;

}

returnlen;}

最長公共子序列（LCS）沒看懂沒看懂沒看懂

給出兩個字元串a, b，求它們的最長、連續的公共字串。

這很容易就想到以DP[I][J]表示A串比對到I，B串比對到J時的最大長度。則：

0 I==0|| J==0

DP[I][J]=DP[I-1][J-1]+1 A[I]==B[J]

MAX（DP[I-1][J]，DP[I][J-1]）不是以上情況

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

//最長公共子序列

const int SIZE=1001;

int dp[2][SIZE]; //兩個一維數組

//輸入兩個字元串，傳回最大的長度

int LCS(const string& a,conststring& b) {

int i,j,flag;

memset(dp,0,sizeof(dp)); //memset（）是初始化dp數組都為0。。

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;

}

return dp[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]

這樣實作的空間複雜度為O(VN)，實際上可以優化到O（V）。以下是代碼：

const int MAXW=13000; //最大重量

const intMAXN=3450; //最大物品數量

int c[MAXN]; //物品的存放要從下标1開始

int w[MAXN]; //物品的存放要從下标1開始

int dp[MAXW];

//不需要将背包裝滿，則将DP數組全部初始化為0

//要将背包裝滿，則初始化為DP[0]=0，DP[1]…DP[V]=-1(即非法狀态)

int Packet(int n,int v) {

int i,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]);

}

return dp[v];}

完全背包問題

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的大小是c[i]，價值是w[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背包的優化原理。在優化的代碼中，之是以第二重循環是倒序，是為了防止重複拿，那麼隻要将其變為順序即可以重複取。代碼就不給了。

多重背包問題

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

這題仍然可以用到上一題的思想，DP表示狀态與上面的相同。方程為：

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種物品分成若幹件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分别為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。然後用01背包做，這樣的複雜度為O(V*Σlog n[i])。關鍵代碼：

const int SIZE=1001;

int dp[SIZE];

int num[SIZE],c[SIZE],w[SIZE]; //num[i]是I物品的件數,C[I]是費用，W[I]是價值

int MultiPack(int n,int v) { //存入參數，N是物品種類數，V是背包容量

int i,j,k;

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

for(i=1;i<=n;++i) { //存放物品的數組下标從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]);

}

return dp[v];

}

狀态表示總結

一維的狀态表示

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

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

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

有一些題是DP與暴力相結合，如POJ 3267 The Cow Lexicon這題。大意是給出一個長的字元串，還有若幹個短的字元串，問長字元中至少要删除幾個字元才能使得長字元串中的子字元串都與某個短字元串相對應。dp[i]表示從I到LEN-1需要删除的最少字元串數，則dp[i]=min(dp[i+1]+1，dp[k]+del)其中dp[i+1]+1是沒有找到比對的情況，dp[k]+del是有比對的情況,K表示從I開始比對,到比對完後的最後一個字元的位置,DEL表示在比對過程中要删除的字元數。由于方程的特點，要從最後一個字元向第一個字元推去。中間要删除的字元數用暴力找出。

有一些題用DP來枚舉全部的範圍，如POJ 1925 Spiderman這題。用DP[I]表示到達這個位置的最小跳數。其中DP數組為dp[1000005]，這是可能跳到的全部範圍。

二維狀态表示

通常是用來處理兩種事物。DP[I][J]通常表示A的前I個和B的前J個XX的最優值。

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是表示某某狀态得到的結果。

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方程舉個例：POJ 3280 Cheapest Palindrome這題。大意是給出一個字元串，你可在任意位置增加或删除字元，每增加或删除一個字元都有一個對應的代價，求将其變為回文串的最小代價。以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其實作方法如下所示：

for(t=1;t<len;++t){ //間隔為t

for(i=1;i<len;++i) { //起始位置

if( i+t<=len ) {

j=i+t;

//do your work

}

有一些題看似一維，可将之變為二維。如：POJ1159 Palindrome 這題。大意是給出一個字元，求将其變為回文串要加入的最少字元數。得到字元串後，再構造一個逆串，然後求其LCS。最後将字元串長度減去LCS數就是結果。

有時可以将DP與HASH相結合。如：POJ 1054 The Troublesome Frog這題。大意是在一個坐标系中給出N個點，求找出以哪兩點作一條直線經過的點數最多。以DP[I][J]表示過第J點和第I點的直線一共經過的點數。DP[I][J]=（DP[J][INDEX]+1，-INF），先算出INDEX這點的坐标，然後用哈希查找，如果找到，則執行DP[J][INDEX]+1，如果找不到則用-INF表示不存在。

對于整除類型的題，如果要用DP做，那麼其中有一維通常是佘數。如：POJ 1745Divisibility這題，dp[i][j]表示對前I個數進行了處理,餘數為J的情況

帶偏移的狀态表示

DP的表示形式通常為：DP[I][J]表示到第I個XX時，YY與ZZ之差為J時的最優值。例如：POJ 1837這題。

題目大意：給出天平c個挂鈎的位置,然後給出g個物品的品質,将物品挂在天平上,問使天平平衡的方法有幾種。

思想：用l[i]表示第i個點的x坐标值，用w[i]表示第i個砝碼的重量，用dp[i][j]表示加了i個砝碼，兩邊力矩之差為j的可能方法數，則本題隻要計算出dp[i][0]，即最終力矩差為0的方法數即可。由于品質差可能為負，這裡加上一個偏移量，考慮原題的資料可知，要想平衡，則一邊力矩至多為15*25*10=3750，故每個j加上3750。狀态轉移方程：dp[i+1][k+w[i]*l[j]]+=dp[i][k]，i=0~g，j=0~c，k=0~7500。輸出結果：dp[w][3750]

動态規劃變态總結 by zeus

1：Pku acm 1163 the Triangle

2：Pku acm 1953 World Cup Noise //說白了就是斐波那切數列

3：Pku acm 1458 Common Subsequence Lcs

4：Pku acm 2250 Compromise記錄路徑的lcs

5：Pku acm 1159 Palindrome 回文串

6：Pku acm 1080 Humman Gene Function

7：Pku acm 2192 Zipper 判斷2個字元串能否組成1個字元串

8：Pku acm 3356 AGTC 一個字元串到另一個的最小步驟

9：Pku acm 1887 Testing the CATCHER最長下降子序列

10：Pku acm 2533 Longest Ordered Subsequence最長上升子序列

11：Pku acm 1631 Bridging signals最長上升子序列的加強版….二分法

12：Pku acm 1157 LITTLE SHOP OF FLOWERS

13：Pku acm 1088 滑雪

14：Pku 1050 To the Max

15：Pku 1050 To the Max最大線段和的加強闆…..二維的

16：Pku 1014 dividing

17: Pku acm 1160 post office

18: pku acm 1015 Jury Compromise

19: hdoj 2546飯卡

20:pku 1837 Balance

21: pku 3267 The Cow Lexicon

22:Pku 1742 Coins

//走塔....經典的dp

#include "iostream"

using namespace std;

int max(int a,int b)

{

return a>b?a:b;

}

int main()

{

int n,i,j;

int a[100][100];

int f[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];

else

f[j]=f[j+1]+a[i][j];

}

printf("%d\n",f[0]);

}

system("pause");

}

2：Pku acm 1953 World Cup Noise //說白了就是斐波那切數列

#include "iostream"

using namespace std;

int main()

{

int n,m;

int i;

int f[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：Pku acm 1458 Common Subsequence Lcs經典

#include"iostream"

#include"cstring"

usingnamespace std;

intsetmax(int a,int b)

{

if(a>b)

return a;

else return b;

}

int f[8100][8100];

main()

{

char s1[800];

char s2[800];

int i,j;

int sl1,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;

else

f[i][j]=setmax(f[i-1][j],f[i][j-1]);

}

printf("%d\n",f[i-1][j-1]);

}

4：Pku acm 2250 Compromise記錄路徑的lcs

#include"iostream"

#include"string"

usingnamespace std;

#define N100

struct node

{

string s;

}s1[N],s2[N];

intf[N][N];

intpath[N][N];

string temp;

int flag;

void lcs(int i,int j)

{

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;}

else

cout<<s1[i-1].s<<" ";}

}

else

if(path[i][j]==2) lcs(i-1,j);

else lcs(i,j-1);

}

int main()

{

int i=0,j;

int len1,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;

}

else if(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：Pku acm 1159 Palindrome 回文串

帶有些許優化的lcs

#include "iostream"

#include "string"

#include "algorithm"

using namespace std;

int a[5005],b[5005];

int c[3],d[3];

string s1,s2;

int main()

{

int m,n=0;

int i,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;

}

else if(b[j]>a[j+1])

{

b[j+1]=b[j];

}

else if(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：Pku acm 1080 Humman Gene Function

#include "iostream"

using namespace std;

int f[250][250];

int g[250][250];

char s1[180];

char s2[180];

int maxnum(intx,int y,int z)

{

int zz= x>y?x:y;

return zz>z?zz:z;

}

void make()

{

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;

}

int sw(char ch)

{

if(ch=='A') return 1;

else if(ch=='C') return 2;

else if(ch=='G') return 3;

else if(ch=='T') return 4;

elseif(ch=='-') return 5;

}

int find(char ch1,char ch2)

{

return f[sw(ch1)][sw(ch2)];

}

int main()

{

make();

int sl1,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：Pku acm 2192 Zipper 判斷2個字元串能否組成1個字元串

//用動态規劃解決，ok[i][j]表示str1長度為i的字首和str2長度為j的字尾能否組成目标中str中長度為i+j的字首串

#include "iostream"

using namespace std;

int i,j,n;

int sl1,sl2,sl3;

char s1[500],s2[500],s3[500];

int f[500][500];

int main()

{

int count=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;

else

break;

}

for(i=0;i<strlen(s2);i++)

{

if(s2[i]==s3[i])

f[0][i+1]=1;

else

break;

}

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("Data set %d:",count);

if(f[sl1][sl2]==1)

printf("yes\n");

else

printf("no\n");

}

8：Pku acm 3356 AGTC 一個字元串到另一個的最小步驟

#include "iostream"

#include "string"

using namespace std;

int setmin(intx,int y,int z)

{

int xx=x>y?y:x;

return xx>z?z:xx;

}

string s1,s2;

int f[1005][1005];

int main()

{

int n,m;

int i,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]);

else

f[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：Pku acm 1887 Testing the CATCHER最長下降子序列

#include "iostream"

using namespace std;

int a[32769],f[32769];

int main()

{

int i,j,n,max;

int count=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(" maximum possible interceptions:%d\n\n",max);

}

10：Pku acm 2533 Longest Ordered Subsequence最長上升子序列

#include"iostream"

using namespacestd;

int f[10000];

int a[10000];

int main()

{

int n,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：Pku acm 1631 Bridging signals最長上升子序列的加強版….二分法

#include "iostream"

#include "string"

using namespace std;

#define N50000

int f[N];

int a[N];

int main()

{

int n,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];

int s=1;

int l,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：Pku acm 1157 LITTLE SHOP OF FLOWERS

該題也是經典的動态規劃，題目叙述的依然很麻煩，其實簡化一下就是這樣的：例如下面這個例子就是：3表示行，5表示列，然後在下面的3行5列每一行選一個數，使這3個數最大，要求選的數列數必須依次增大，就是從左上方想右下方選3個數使和最大。

3 5

7 23 -5 -24 16

5 21 -4 10 23

-21 5 -4 -20 20

#include "iostream"

using namespace std;

#define N5000

intf[N][N];

int w[N][N];

int main()

{

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];

}

int max=-50000;

for(i=0;i<=m;i++)

if(f[n][i]>max)

max=f[n][i];

printf("%d\n",max);

}

13：Pku acm 1088 滑雪

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。輸出最長區域的長度。

#include "iostream"

using namespace std;

int h[100][100];

int f[100][100];

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int r,c;

bool judge(int x,int y)

{

if(x>=0&&y>=0&&x<r&&y<c)

return true;

else return false;

}

int dp(int i,int j)

{

int max=0,xi,yi,k;

if(f[i][j]!=0) return f[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])

{

int num=dp(xi,yi);

if(num>max)

max=num;

}

f[i][j]=max+1;

returnmax+1;

}

int main()

{

int i,j;

int temp,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：hdoj1003 max num

#include "iostream"

using namespace std;

int f[100005];

int a[100005];

int main()

{ int num,n,i,j;

int st,end,now,max;

int flag;

int count=0;

int k;

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");

}

return 0;

}

15：Pku 1050 To the Max最大線段和的加強闆…..二維的

#include "iostream"

using namespace std;

int n,i,j,cnt,now,maxx,k;

int a[150][150];

int s[150][150][150];

int main()

{

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);

}

return 0;

}

16：Pku 1014 dividing

實在不會做先抄個代碼

#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]){return 1;} //讀到末行

num++;

printf("Collection #%d:\n",num);

mid=0;

for(int i=1;i<=6;i++) mid+=stone[i]*i;

if (mid % 2 ==1)//明顯的剪枝

{

printf("Can't be divided.\n\n");

return 2;

}

else mid/=2;//我們的任務就是求opt

return 0;

}

voiddp()

{

memset(opt,0,60000);//初始化，opt所有成員為false

opt[0]=true; //opt[0]顯然是true

max=0; //目前最大值是0

for (int i=1;i<=6;i++)

{

if (stone[i]>0)

{

for(int j=max;j>=0;j--) // 從目前最大值開始往下算

if (opt[j]) //找到可行的j

{

if (opt[mid]) //判斷是否已經求出結果

{

printf("Can bedivided.\n\n");

return;

}

for (intk=1;k<=stone[i];k++)//在剛找到的可行j基礎上加石頭.

{

if (j+k*i>mid || opt[j+k*i]) break; //如果已經大于總價值的一半mid，或opt[j+k*i]已計算，跳出循環

opt[j+k*i]=true;

}

max=max+i*stone[i]; //更新目前最大值

if (max>mid) max=mid; //如果目前最大值超過了mid，對其指派為mid

}

printf("Can't be divided.\n\n"); //如果從1到6循環完一遍後仍然沒有算出opt[mid]，說明無解

}

intmain()

{

while (1)

{

int t=input();

switch (t)

{

case 1 : return 0; //讀到末行，結束

case 2 : continue; //讀到明顯的剪枝

default : dp();

}

return 0;

}

17: Pku acm 1160 post office

貼代碼

題目給出m個村莊及其距離，給出n個郵局，要求怎麼建n個郵局使代價最小。

思路：用opt[i][j]記錄把前i個郵局建到前j個村莊中的最優解，用cost[i][j]記錄所有在i到j村莊中，建1個郵局的最小代價。顯然郵局應該設到中點。讓前i個郵局覆寫前j個村莊，第i+1個郵局覆寫第j+1至j+k個村莊(j+k<=n)，則狀态轉移方程為

w[i+1][j+k]=min{w[i][j]+cost[j+1][j+k];}(k+j<=n)

Cost數組存放從i到j中有一個郵局的最小代價，顯然該郵局應該放在中間

W[i][j] 表示前i個郵局覆寫前j個村莊的最小代價，對于i=1來說，w[i][j] = cost[i][j],讓前2個郵局覆寫前j個村莊，也就是i=2的情況，可能是一下情況的最優解：第一個郵局覆寫第一個村莊，第二個村莊覆寫2-j個村莊，或者第一個郵局覆寫第1-2個村莊，第二個村莊覆寫3-j個村莊，第一個郵局覆寫第1-3個村莊，第二個村莊覆寫4-j個村莊，等等等等

#include "iostream"

using namespace std;

int cost[310][310];

int w[310][310];

#define max 3000000

int main()

{

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]);

}

return 0;

}

18: pku acm 1015 Jury Compromise

題目大意：在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決定。陪審團是由法官從公衆中挑選的。先随機挑選n個人作為陪審團的候選人，然後再從這n個人中選m人組成陪審團。選m人的辦法是：控方和辯方會根據對候選人的喜歡程度，給所有候選人打分，分值從0到20。為了公平起見，法官選出陪審團的原則是：選出的m個人，必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同，那麼選辯控雙方總分之和最大的方案即可。

分析：顯然本題如不用DP的話，顯然會逾時。我們将第i個人的辯方和控方的差記錄在sub[i]中，将第i個人的辯方和控方的和記錄在plus[i]中，現在用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是不是已經在方案f(j-1,x)中。此時，我們可以用一個path(j,k)來記錄相應的f(j,k)中最後選的人。例如上面的,則path(j,k)=i;倒數第二個人選的編号為path(j-1,k-sub[i]),依次類推，我們就能求出某個方案中所有人的編号。實際解題中，則于控辯差有可能為負，由于控辯差的範圍為[-21*m,21*m]我們可将所有控辯差加上m*21來解決，保證其值為正。

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

int m,n;

int f[21][850];

intpath[21][850];

intPLUS[500],sub[500],ans[21],la,size;

int main()

{

int i,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個人有沒有出現過

{

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++)//取絕對值最小的作為最優解

{

if(f[m][size+j]>=0||f[m][size-j]>=0)

{

if(f[m][size+j]>f[m][size-j])

i=size+j;

else i=size-j;

break;

}

cout<<"Jury #"<<test++<<endl;

cout<<"Best jury has value"<<(f[m][i]+i-size)/2<<" for prosecution and value"<<(f[m][i]-i+size)/2<<" for defence:"<<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;

}

return 0;

}

19: hdoj 2546飯卡

電子科大學部食堂的飯卡有一種很詭異的設計，即在購買之前判斷餘額。如果購買一個商品之前，卡上的剩餘金額大于或等于5元，就一定可以購買成功（即使購買後卡上餘額為負），否則無法購買（即使金額足夠）。是以大家都希望盡量使卡上的餘額最少。

某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的餘額，問最少可使卡上的餘額為多少。

Input

多組資料。對于每組資料：

第一行為正整數n，表示菜的數量。n<=1000。

第二行包括n個正整數，表示每種菜的價格。價格不超過50。

第三行包括一個正整數m，表示卡上的餘額。m<=1000。

n=0表示資料結束。

Output

對于每組輸入,輸出一行,包含一個整數，表示卡上可能的最小餘額。

Sample Input

1 2 3 2 1 1 2 3 2 1

Sample Output

-45

#include <iostream>

#include <algorithm>

using namespace std;

int a[1002];

int b[1002];

void dfs(intx);

int m;

intsum,num,ans,flag;

int main()

{

int i,j,k,n,t;

while(scanf("%d",&n)!=EOF&& n)

{

memset(b,0,sizeof(b));

sum = 0;

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

sum += a[i];

}

scanf("%d",&m);

if (sum+5 <= m) //如果餘額很大的情況

{

printf("%d\n",m-sum);

continue;

}

if (m < 5) //如果本來的餘額小于5那麼就不用計算了

{

printf("%d\n",m);

continue;

}

sort(a,a+n);

//開始周遊:

//找到臨界大于m-5的最小的和

ans = 0;

num = m - 5;

for(i=n-2;i>=0;i--)

{

int maxnum = 0;

for(j=i+1;j<=n-2;j++)

{

if((b[j] > maxnum)&& (a[i]+b[j]<=num) )

maxnum = b[j];

}

if(a[i]+maxnum == num)

{

ans = num;

break;

}

else if(a[i]+maxnum < num)

{

b[i] = a[i]+maxnum;

}

if(b[i] > ans)

ans = b[i];

}

printf("%d\n",m-ans-a[n-1]);

}

return 0;

}

20:pku 1837 Balance

輸入一個天平若幹（<=20）挂鈎的位置，将若幹（<=20）砝碼挂到天平上，問有多少種使天平挂平衡的方法。

解題思路：

用一個二維數組a[x][y+mid]記錄挂x個砝碼時到y這個值的方法數，将砝碼一一挂上，最後記錄所有砝碼都挂上時的t[x][MID]的值，詳見代碼。

狀态方程:a[i][j+value[i]*hook[k]]+=a[i-1][j];背包問題

#include "stdio.h"

#include "stdlib.h"

#define MID 7500

int a[21][2*MID];

int val[21];

int hook[21];

int main()

{

intm,n;

inti,j,k;

while(scanf("%d%d",&m,&n)!=EOF)

{

memset(a,0,sizeof(a));

for(i = 1;i<=m;i++)

scanf("%d",&hook[i]);

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

scanf("%d",&val[i]);

for(j = 1;j<=m;j++)

a[1][val[1]*hook[j]+MID]++;

for(i =2;i<=n;i++ )

for(j = 0;j<=2*MID;j++)

for(k = 1;k<=m;k++)

if(a[i-1][j]!=0)

{

a[i][j+val[i]*hook[k]]+=a[i-1][j];

}

printf("%d\n",a[n][MID]);

}

return 0;

}

21: pku 3267 The Cow Lexicon

題目意思就是給出一個字元序列，同時給出已知的字元序列（單詞），問至少需要去掉多少個字元之後能夠将給出的字元序列變成已知的字元序列（單詞）的組合（根據題目意思，沒有字元是已知字元序列組合的一種情況）。

可以用s[i]表示從第一個字元到第i個字元中，滿足題目要求去掉的最少字元數。那麼s[i]=min（num[k，i]+s[k-1]），其中num[k，i]表示從第k個字元到第i個字元比對到某一個單詞時所需要的去掉的最少字元數。當然比對時是需要窮舉所有的單詞的。比對的時候如果從前往後比較的話，需要加入剪枝（如果k+len[j]〉i的話肯定就是不行的），這樣的話就可以采取從後往前的比較方式，這樣之前需要将每個單詞的長度儲存到len[j]當中。

#include <iostream>

#include <stdlib.h>

#include "string.h"

using namespace std;

int main(int argc, char *argv[])

{

char word[601][30],str[305];

inti,j,k,num,s[305],min,len[601],m,l,pos_str,pos_word;

while(scanf("%d%d",&m,&l)!=EOF){

scanf("%s",str+1);

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

scanf("%s",word[i]+1);

len[i]=strlen(word[i]+1);

}

s[0]=0;

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

min=i;

for(j=1;j<=m;j++){

pos_str=i;

pos_word=len[j];

num=0;

while(pos_str>=1&&pos_word>=1){

if(str[pos_str]==word[j][pos_word]){

pos_str--;

pos_word--;

}

else {

pos_str--;

num++;

}

if(pos_word<=0 &&min>num+s[pos_str]){

min=num+s[pos_str];

}

s[i]=min;

}

printf("%d\n",s[l]);

}

system("PAUSE");

return 0;

}

22:Pku 1742Coins

編寫一個程式，讀入n，m。有币值A1、A2、A3…、An的硬币，對應各有C1、C2、C3、…、Cn數量的硬币，問它們能夠在1~m元中組合成多少中不同的币值？

#include<iostream>

using namespace std;

inta[110],c[110];

int dp[2][100010],flag[100010],flagans[100010];

int main()

{

int n,m;

while(scanf("%d%d",&n,&m)!=EOF&&!(n==0&&m==0))

{

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

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

scanf("%d",&a[i]);

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

scanf("%d",&c[i]);

for(int i=0;i<2;i++)

dp[i][0]=1;

memset(flag,0,sizeof(flag));

memset(flagans,0,sizeof(flagans));

int from=0,to=1;

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

{

memset(flag,0,sizeof(flag));

for(int j=1;j<=m;j++)

{

dp[to][j]=dp[from][j];

if(dp[to][j]==0&&j>=a[i]&&dp[to][j-a[i]]&&flag[j-a[i]]+1<=c[i])

{

dp[to][j]=1;

flagans[j]=1;

flag[j]=flag[j-a[i]]+1;

}

int temp;

temp=from;

from=to;

to=temp;

}

int ans=0;

for(int i=1;i<=m;i++)

{

// cout<<i<<" "<<flagans[i]<<endl;

ans+=flagans[i];

}

printf("%d\n",ans);

}

system("pause");

return 0;

}

動态規劃總結——經典問題總結

最長上升子序列（LIS）

最長公共子序列（LCS） 沒看懂沒看懂沒看懂

01背包

完全背包問題

多重背包問題

一維的狀态表示

二維狀态表示

帶偏移的狀态表示

最長公共子序列（LCS）沒看懂沒看懂沒看懂