动态规划练习题含答案

《动态规划练习题含答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划练习题USACO2.2SubsetSums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：and{1,2}这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:{1,6,7}and{2,3,4,5}{注1+6+7=2+3+4+5}{2,5,7}and{1,3,4,6}{3,4,7}and{1,2,5,6}{1,2,4

2、,7}and{3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。PROGRAMNAME:subsetINPUTFORMAT输入文件只有一行，且只有一个整数NSAMPLEINPUT(filesubset.in)7OUTPUTFORMAT输出划分方案总数，如果不存在则输出0。SAMPLEOUTPUT(filesubset.out)4参考程序如下：#includeusingnamespacestd;constunsignedintMAX_SUM=1024;intn;unsignedlonglongintd

3、yn[MAX_SUM];ifstreamfin("subset.in");ofstreamfout("subset.out");intmain(){fin>>n;fin.close();ints=n*(n+1);if(s%4){fout<<0<=i;j--)dyn[j]+=dyn[j-i];fout<<(dyn[s]/2)<

4、在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。如果一个集合P中的元素可以通过串联（允许重复；串联，相当于Pascal中的“+”运算符）组成一个序列S，那么我们认为序列S可以分解为P中的元素。并不是所有的元素都必须出现。举个例子，序列ABABACABAAB可以分解为下面集合中的元素：{A,AB,BA,CA,BBC}序列S的前面K个字符称作S中长度为K的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。PROGRAMNAME:prefixINPUTFORMAT输入

5、数据的开头包括1..200个元素（长度为1..10）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个“.”的行。集合中的元素没有重复。接着是大写字母序列S，长度为1..200,000，用一行或者多行的字符串来表示，每行不超过76个字符。换行符并不是序列S的一部分。SAMPLEINPUT(fileprefix.in)AABBACABBC.ABABACABAABCOUTPUTFORMAT只有一行，输出一个整数，表示S能够分解成P中元素的最长前缀的长度。SAMPLEOUTPUT(fileprefix.out)11示例程序

6、如下：#include#defineMAXP200#defineMAXL10charprim[MAXP+1][MAXL+1];intnump;intstart[200001];chardata[200000];intndata;intmain(intargc,char**argv){FILE*fout,*fin;intbest;intlv,lv2,lv3;if((fin=fopen("prim.in","r"))==NULL){perror("fopenfin");exit(1);}if((fout=fopen("prim.out","w"))==NULL){

7、perror("fopenfout");exit(1);}while(1){fscanf(fin,"%s",prim[nump]);if(prim[nump][0]!='.')nump++;elsebreak;}ndata=0;while(fscanf(fin,"%s",data+ndata)==1)ndata+=strlen(data+ndata);start[0]=1;best=0;for(lv=0;lv