acm动态规划例题

《acm动态规划例题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、ProblemA:简单的图形覆盖TimeLimit:1000MS MemoryLimit:65536KTotalSubmit:201Accepted:104Description有一个2*n的方格,要用若干个1*2的模块覆盖,模块可以横放,也可以竖放.问对于给定的n(n<=100),有多少种不同的覆盖方法.Input有多个测试用例,每个用例占一行,为一个正整数nOutput对于每个测试用例,输出一行相应的结果SampleInput911SampleOutput55144分析：f(n)=#includeintA[101];intmain(){intn,i;wh

2、ile(scanf("%d",&n)!=EOF){A[0]=1;A[1]=2;if(n==1

3、

4、n==0)printf("%d",A[0]);elseif(n==2)printf("%d",A[1]);else{for(i=2;i

5、到7.Input第一行输入一个n(1〈N〈=100)表示这一组数有多长,第二行是N个数.测试案例有多个,n=0时结束.Output输出这一组数的最大子段和.SampleInput5-254-37109-38-2898-30-2050-24100SampleOutput1398分析：A-254-37B表示A0~Ai数段中包含第i个元素的最大子段和-259613B[i]=#includeintA[101];intB[101];intmain(){intn,i,max;scanf("%d",&n);while(n!=0){for(i=0;i

6、("%d",&A[i]);B[0]=A[0];for(i=0;i

7、得对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对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度.SampleInputabcfbcabfcabprogrammingcontestabcdmnpSampleOutput420分析Z[i][j

8、]=下标0123456Z[i][j]abcfbc000000001a01111112b01222223f01223334c01233345a01233346b0123344X，Y下标从0开始，Z[i][j]下标有效的从1开始#include#includecharx[201];chary[201];intz[200][200];intmain(){inti,j,s,t,max;while(scanf("%s%s",x,y)!=EOF){s=strlen(x);t=strlen(y);for(i=0;i

9、r(j=0;j=z[i][j-1])z[i][j]=z[i-1][j];elsez[i][j]=z[i][j-1];}}max=z[0][0];for(i=0;i<=s;i++)for(j=0;j<=t;j++)if(z[i][j]>max)max=z[i][j];printf("%d