acm动态规划例题.doc

Problem A:简单的图形覆盖Time Limit:1000MS Memory Limit:65536KTotal Submit:201 Accepted:104 Description 有一个2*n的方格,要用若干个1*2的模块覆盖,模块可以横放,也可以竖放.问对于给定的n(n=100),有多少种不同的覆盖方法.Input 有多个测试用例,每个用例占一行,为一个正整数nOutput 对于每个测试用例,输出一行相应的结果Sample Input 911Sample Output 55144分析：f(n)=#includeint A101;int main() int n,i; while(scanf(%d,&n)!=EOF) A0=1;A1=2; if(n=1|n=0) printf(%dn,A0); else if(n=2) printf(%dn,A1); else for(i=2;in;i+) Ai=Ai-1+Ai-2; printf(%dn,Ai-1); return 0;Problem B:最大子段和Time Limit:1000MS Memory Limit:65536KTotal Submit:574 Accepted:299 Description 有一组数,如-2 5 4 -3 7 的最大子段和是13, 是从5到7.Input 第一行输入一个n(1 N=100 ) 表示这一组数有多长,第二行是N个数. 测试案例有多个,n=0时结束. Output 输出这一组数的最大子段和.Sample Input 5-2 5 4 -3 7109 -3 8 -28 98 -30 -20 50 -24 100Sample Output 1398分析：A -254-37B 表示A0Ai数段中包含第i个元素的最大子段和-259613Bi=#includeint A101;int B101;int main() int n,i,max; scanf(%d,&n); while(n!=0) for(i=0;in;i+) scanf(%d,&Ai); B0=A0; for(i=0;in;i+) if(Bi-10) Bi=Ai; else Bi=Bi-1+Ai; max=B0; for(i=1;in;i+) if(maxBi) max=Bi; printf(%dn,max); scanf(%d,&n); return 0;Problem C:最长公共子序列Time Limit:1000MS Memory Limit:65536KTotal Submit:164 Accepted:99 Description 我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列,使得对j=1,2,.k,有Xij=zj.比如Z=a,b,f,c是X=a,b,c,f,b,c的子序列.现在给出两个序列X和Y,任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列.Input 输入包括多组测试数据.每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列.两个字符串之间由若干个空格9开.Output 对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度.Sample Input abcfbc abfcabprogramming contestabcd mnpSample Output 420分析Zij= 下标0123456Zijabcfbc000000001a01111112b01222223f01223334c01233345a01233346b0123344X，Y下标从0开始，Zij 下标有效的从1开始#include#includechar x201;char y201;int z200200;int main() int i,j,s,t,max; while(scanf(%s%s,x,y)!=EOF) s=strlen(x);t=strlen(y); for(i=0;is;i+) zi0=0; for(j=0;jt;j+) z0j=0;for(i=1;i=s;i+)for(j=1;j=zij-1) zij=zi-1j; else zij=zij-1;max=z00;for(i=0;i=s;i+)for(j=0;jmax) max=zij;printf(%dn,max); return 0;Problem D:最长上升子序列Time Limit:1000MS Memory Limit:65536KTotal Submit:456 Accepted:239 Description 一个数的序列bi,当b1=b2=b3.=bn的时候,称这个序列是上升的。对于给定的一个序列(A1,A2,.,AN),可以得到一些上升的子序列(AI1,AI2,.AIK,这里1=I1=I2=.=IK=N,比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等.这些子序列中最长的长度是4,比如子序列(1,3,5,8). 你的任务就是对于给定的序列,求出最长上升子序列的长度. Input 输入有多个案例，每个案例占两行： 第一行是序列的长度N(1=N=1000).第二行给出序列中的N个整数,这些整数的取值范围都在0到10000. Output 最长上升子序列的长度.Sample Input 71 7 3 5 9 4 821036 3Sample Output 41分析A1735948B1223434#includeint A100,B100;int main()int n,i,j,max;while(scanf(%d,&n)!=EOF)for(i=0;in;i+)scanf(%d,&Ai);B0