动态规划总结经典题目(经典中的经典)_动态规划例题总结

2020-02-28 其他工作总结下载本文

动态规划总结经典题目(经典中的经典)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“动态规划例题总结”。

动态规划总结——经典问题总结

本文着重讨论状态是如何表示，以及方程是怎样表示的。当然，还附上关键的，有可能作为模板的代码段。但有的代码的实现是优化版的。

经典问题总结

最长上升子序列（LIS）

问题描述如下:

设L=是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=，其中k1 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开始 int len(1),low,high,mid,i;

dp[1]=data[1];for(i=1;i

while(lowdp[mid]){ low=mid+1;} else {

high=mid-1;} }

dp[low]=data[i];if(low>len){ ++len;} }

return len;}

最长公共子序列（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,const string& b){ int i,j,flag;

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

flag=1;

for(i=1;i

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

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 int MAXN=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

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

有更好的做法，那就是利用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

有更好的想法就是先用二进制来划分。将第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=v){ for(j=c[i];j

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

else { //使用二进制划分 k=1;

while(k=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

有一些题可能要将一些额外的东西也认为是物品。如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

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

有时可以将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]

动态规划变态总结

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

for(j=0;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

if(f[j]>f[j+1])

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

else

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

}

printf(“%dn”,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

{

f[i]=f[i-1]+f[i-2];

}

for(i=0;i

{

scanf(“%d”,&m);

{

printf(“Scenario #%d:n%dnn”,i+1,f[m-1]);

}

} }

3：Pku acm 1458 Common Subsequence Lcs经典 #include “iostream” #include “cstring” using namespace std;int setmax(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

{

f[0][i]=0;

f[i][0]=0;

}

for(i=1;i

for(j=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(“%dn”,f[i-1][j-1]);

} } 4：Pku acm 2250 Compromise记录路径的lcs #include “iostream” #include “string” using namespace std;#define N 100 struct node {

string s;}s1[N],s2[N];int f[N][N];int path[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

flag=1;}

else

cout

}

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

for(j=0;j

if(i==j)f[i][j]=1;

for(i=1;i

for(j=1;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

} }

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

{

b[0]=0;

for(j=0;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]

{

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

}

for(j=0;j

a[j]=b[j];

}

printf(“%dn”,n-b[n]);14

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(int x,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;

else if(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

g[0][i] = g[0][i-1]+find('-',s2[i-1]);

for(i=1;i

g[i][0] = g[i-1][0]+find(s1[i-1],'-');

for(i=1;i

for(j=1;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

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

{

if(s1[j]==s3[j])

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

else

break;

}

for(i=0;i

{

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

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

else

break;

}

for(i=0;i

for(j=0;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(“yesn”);

else

printf(“non”);

} }

8：Pku acm 3356 AGTC 一个字符串到另一个的最小步骤

#include “iostream” #include “string” using namespace std;int setmin(int x,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

f[i][0]=i;

for(i=0;i

f[0][i]=i;

for(i=1;i

for(j=1;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

} }

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

{

f[i]=1;

for(j=0;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 poible interceptions: %dnn”,max);

} }

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

#include “iostream” using namespace std;int f[10000];int a[10000];int main(){

int n,i,j,max;

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

{

for(i=0;i

{

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

}

memset(f,0,sizeof(f));

max=0;

for(i=1;i

{

f[i]=1;

for(j=0;j

if(a[j-1]f[i])

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

if(f[i]>max)

max=f[i];

}

printf(“%dn”,max);

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

#include “iostream” #include “string” using namespace std;#define N 50000 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

{

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

// f[i]=a[i];

}

f[1]=a[0];

int s=1;

int l,r,mid;

for(i=1;i

{

if(f[s]

f[++s]=a[i];

else

{

l=0;

r=s;

mid=(l+r)>>1;

while(l

{

mid=(l+r)>>1;

f[mid]

}

f[l]=a[i];

}

printf(“%dn”,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 N 5000 int f[N][N];int w[N][N];int main(){

int n,m,i,j,k;while(cin>>n>>m){

for(i=0;i

for(j=0;j

cin>>w[i][j];

for(i=0;i

for(j=0;j

f[i][j]=-50000;

for(i=1;i

f[1][i]=w[0][i-1];

for(i=2;i

{

for(j=1;j

{

if(j>=i)

for(k=1;k

if(f[i][j]

f[i][j]=f[i-1][k]+w[i-1][j-1];

}

int max=-50000;

for(i=0;i

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

max=f[n][i];

printf(“%dn”,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

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

{

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;

return max+1;} int main(){

int i,j;

int temp,max;

while(cin>>r>>c)

{

for(i=0;i

for(j=0;j

{

cin>>h[i][j];

}

memset(f,0,sizeof(f));

max=0;

for(i=0;i

{

for(j=0;j

{

temp=dp(i,j);

max=max>temp?max:temp;

}

cout

} }

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

cin>>a[i];

now=0;

max=-999;

k=1;

for(i=0;i

{

now+=a[i];

if(now>max)

{

max=now;

end=i+1;

st=k;

}

if(now

{

now=0;

k=i+2;

}

printf(“Case %d:n”,count);

printf(“%d %d %dn”,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

for(j=1;j

{

scanf(“%d”,&a[i][j]);

s[i][i][j]=a[i][j];

}

for(i=1;i

for(j=i+1;j

for(k=1;k

{

s[i][j][k]=s[i][j-1][k]+a[j][k];

}

maxx=0;

for(i=1;i

for(j=1;j

{

cnt=0;

now=0;

for(k=1;k

{

cnt+=s[i][j][k];

if(cnt>now)

now=cnt;

if(cnt

cnt=0;

}

if(now>maxx)maxx=now;

}

printf(“%dn”,maxx);

}

return 0;}

16：Pku 1014 dividing

实在不会做先抄个代码 #include

bool opt[60000];

int num=0;

int mid,max;

int stone[7];

int input()

{

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

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

{

printf(“Can't be divided.nn”);

return 2;

}

else mid/=2;//我们的任务就是求opt

return 0;

}

void dp()

{

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

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

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

for(int i=1;i

{

if(stone[i]>0)

{

for(int j=max;j>=0;j--)

// 从当前最大值开始往下算

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

{

if(opt[mid])

//判断是否已经求出结果

{

printf(“Can be divided.nn”);

return;

}

for(int k=1;k

{

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.nn”);//如果从1到6循环完一遍后仍然没有算出opt[mid]，说明无解

}

int main()

{

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

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(){ int i,j,k,m,n,mid,q,v[310];while(scanf(“%d%d”,&m,&n)!=EOF){

for(i=1;i

scanf(“%d”,&v[i]);

memset(cost,0,sizeof(cost));

for(i=1;i

for(j=i;j

{

mid=(i+j)/2;

for(k=i;k

cost[i][j]=cost[i][j]+v[mid]-v[k];

for(k=mid+1;k

cost[i][j]=cost[i][j]+v[k]-v[mid];

}

for(i=0;i

for(j=0;j

w[i][j]=max;

w[0][0]=0;

for(i=0;i

for(j=0;j

if(w[i][j]

{

for(k=1;k

{

q=w[i][j]+cost[j+1][j+k];

if(w[i+1][j+k]>q)

w[i+1][j+k]=q;

}

printf(“%dn”, 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

#include #include #include using namespace std;

int m,n;int f[21][850];int path[21][850];int PLUS[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

{

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

{

if(f[1][size+sub[i]]

{

path[1][size+sub[i]]=i;

f[1][size+sub[i]]=PLUS[i];

}

for(i=1;i

{

for(j=0;j

{

if(path[i][j]>=0)

{

for(k=1;k

{

if(f[i+1][j+sub[k]]

{

for(jj=i,ii=j;jj>=1;jj--)//顺藤摸瓜.判断第k个人有没有出现过

{

if(path[jj][ii]==k)break;

ii-=sub[path[jj][ii]];

}

if(jj

{

path[i+1][j+sub[k]]=k;

f[i+1][j+sub[k]]=f[i][j]+PLUS[k];

}

for(j=0;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

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

cout

}

return 0;

prosecution and value }

19: hdoj 2546饭卡

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。

某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。Input 多组数据。对于每组数据：

第一行为正整数n，表示菜的数量。n

第二行包括n个正整数，表示每种菜的价格。价格不超过50。第三行包括一个正整数m，表示卡上的余额。m

Output 对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。Sample Input 1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0 Sample Output-45 32

#include

using namespace std;

int a[1002];

int b[1002];

void dfs(int x);

int m;

int sum,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

{

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

sum += a[i];

}

scanf(“%d”,&m);

if(sum+5

{

printf(“%dn”,m-sum);

continue;

}

if(m

{

printf(“%dn”,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

{

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

maxnum = b[j];

}

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

{

ans = num;

break;

}

else if(a[i]+maxnum

{

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

}

if(b[i] > ans)

ans = b[i];

}

printf(“%dn”,m-ans-a[n-1]);

}

return 0;

}

20:pku 1837 Balance

输入一个天平若干（

解题思路：

用一个二维数组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(){

int m,n;

int i,j,k;

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

{

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

for(i = 1;i

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

for(i = 1;i

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

for(j = 1;j

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

for(i =2;i

for(j = 0;j

for(k = 1;k

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

{

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

}

printf(“%dn”,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 #include #include “string.h” using namespace std;int main(int argc, char *argv[]){ char word[601][30],str[305];int i,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

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

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

}

s[0]=0;

for(i=1;i

min=i;

for(j=1;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_wordnum+s[pos_str]){

min=num+s[pos_str];

}

s[i]=min;

}

printf(“%dn”,s[l]);

} system(“PAUSE”);

return 0;} 22:Pku 1742 Coins

编写一个程序，读入n，m。有币值A1、A2、A3…、An的硬币，对应各有C1、C2、C3、…、Cn数量的硬币，问它们能够在1~m元中组合成多少中不同的币值？

#include using namespace std;int a[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

scanf(“%d”,&c[i]);for(int i=0;i

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

for(int j=1;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

{

dp[to][j]=1;

flagans[j]=1;

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

}