动态规划练习题(含答案)

动态规划练习题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,7}and{3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。PROGRAMNAME:subsetINPUTFORMAT输入文件只有一行，且只有一个整数NSAMPLEINPUT(filesubset.in)7OUTPUTFORMAT输出划分方案总数，如果不存在则输出0。SAMPLEOUTPUT(filesubset.out)4参考程序如下：#includefstreamusingnamespacestd;constunsignedintMAX_SUM=1024;intn;unsignedlonglongintdyn[MAX_SUM];ifstreamfin(subset.in);ofstreamfout(subset.out);intmain(){finn;fin.close();ints=n*(n+1);if(s%4){fout0endl;fout.close();return;}s/=4;inti,j;dyn[0]=1;for(i=1;i=n;i++)for(j=s;j=i;j--)dyn[j]+=dyn[j-i];fout(dyn[s]/2)endl;fout.close();return0;}USACO2.3LongestPrefix题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。如果一个集合P中的元素可以通过串联（允许重复；串联，相当于Pascal中的“+”运算符）组成一个序列S，那么我们认为序列S可以分解为P中的元素。并不是所有的元素都必须出现。举个例子，序列ABABACABAAB可以分解为下面集合中的元素：{A,AB,BA,CA,BBC}序列S的前面K个字符称作S中长度为K的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。PROGRAMNAME:prefixINPUTFORMAT输入数据的开头包括1..200个元素（长度为1..10）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个“.”的行。集合中的元素没有重复。接着是大写字母序列S，长度为1..200,000，用一行或者多行的字符串来表示，每行不超过76个字符。换行符并不是序列S的一部分。SAMPLEINPUT(fileprefix.in)AABBACABBC.ABABACABAABCOUTPUTFORMAT只有一行，输出一个整数，表示S能够分解成P中元素的最长前缀的长度。SAMPLEOUTPUT(fileprefix.out)11示例程序如下：#includestdio.h#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){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;lvndata;lv++)if(start[lv]){best=lv;for(lv2=0;lv2nump;lv2++){for(lv3=0;lv+lv3ndata&&prim[lv2][lv3]&&prim[lv2][lv3]==data[lv+lv3];lv3++);if(!prim[lv2][lv3])start[lv+lv3]=1;}}if(start[ndata])best=ndata;fprintf(fout,%i\n,best);return0;}USACO3.1ScoreInflation题目如下：我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。我们可以从几个种类中选取竞赛的题目,这里的一个种类是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1=M=10,000)和N,种类的数目1=N=10,000。后面的每一行将包括两个整数来描述一个种类:第一个整数说明解决这种题目能得的分数(1=points=10000),第二整数说明解决这种题目所需的时间(1=minutes=10000)。你的程序应该确定我们应该从每个种类中选多少道题目使得能在竞赛的时间中得到最大的分数。来自任意的种类的题目数目可能任何非负数(0或更多)。计算可能得到的最大分数。PROGRAMNAME:inflateINPUTFORMAT第1行:M,N--竞赛的时间和题目种类的数目。第2-N+1行:两个整数:每个种类题目的分数和耗时。SAMPLEINPUT(fileinflate.in)3004100602501201201003520OUTPUTFORMAT单独的一行包括那个在给定的限制里可能得到的最大的分数。SAMPLEOUTPUT(fileinflate.out)605{从第2个种类中选两题，第4个种类中选三题}示例程序如下：#includefstream.hifstreamfin(inflate.in);ofstreamfout(inflate.out);constshortmaxm=10010;longbest[maxm],m,n;voidmain(){shorti,j,len,pts;finmn;for(j=0;j=m;j++)best[j]=0;for(i=0;in;i++){finptslen;for(j=len;j=m;j++)if(best[j-len]+ptsbest[j])best[j]=best[j-len]+pts;}foutbest[m]endl;//由于数组元素不减，末元素最大}USACO3.3AGame题目如下：有如下一个双人游戏:N(2=N=100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。PROGRAMNAME:game1INPUTFORMAT第一行:正整数N,表示序列中正整数的个数。第二行至末尾:用空格分隔的N个正整数（大小为1-200）。SAMPLEINPUT(filegame1.in)6472952OUTPUTFORMAT只有一行，用空格分隔的两个整数:依次为玩家一和玩家二最终的得分。SAMPLEOUTPUT(filegame1.out)1811参考程序如下：#includestdio.h#defineNMAX101intbest[NMAX][2],t[NMAX];intn;voidreadx(){inti,aux;freopen(game1.in,r,stdin);scanf(%d,&n);for(i=1;i=n;i++){scanf(%d,&aux);t=t[i-1]+aux;}fclose(stdin);}inlineintmin(intx,inty){returnxy?y:x;}voidsolve(){inti,l;for(l=1;l=n;l++)for(i=1;i+l=n+1;i++)best[l%2]=t[i+l-1]-t[i-1]-min(best[i+1][(l-1)%2],best[(l-1)%2]);}voidwritex(){freopen(game1.out,w,stdout);printf(%d%d\n,best[1][n%2],t[n]-best[1][n%2]);fclose(stdout);}intmain(){readx();solve();writex();return0;}USACO3.4RaucousRockers题目如下：你刚刚得到了流行的“破锣摇滚”乐队录制的尚未发表的N(1=N=20)首歌的版权。你打算从中精选一些歌曲，发行M(1=M=20)张CD。每一张CD最多可以容纳T(1=T=20)分钟的音乐，一首歌不能分装在两张CD中。不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：歌曲必须按照创作的时间顺序在CD盘上出现。选中的歌曲数目尽可能地多。PROGRAMNAME:rockersINPUTFORMAT第一行：三个整数：N,T,M.第二行：N个整数，分别表示每首歌的长度，按创作时间顺序排列。SAMPLEINPUT(filerockers.in)4524342OUTPUTFORMAT一个整数，表示可以装进M张CD盘的乐曲的最大数目。SAMPLEOUTPUT(filerockers.out)3参考程序如下：#includestdio.h#defineMAX25intdp[MAX][MAX][MAX],length[MAX];intmain(){FILE*in=fopen(rockers.in,r);FILE*out=fopen(rockers.out,w);inta,b,c,d,best,numsongs,cdlength,numcds;fscanf(in,%d%d%d,&numsongs,&cdlength,&numcds);for(a=1;a=numsongs;a++)fscanf(in,%d,&length[a]);best=0;for(a=0;anumcds;a++)for(b=0;b=cdlength;b++)for(c=0;c=numsongs;c++){for(d=c+1;d=numsongs;d++){if(b+length[d]=cdlength){if(dp[a][c]+1dp[a][b+length[d]][d])dp[a][b+length[d]][d]=dp[a][c]+1;}else{if(dp[a][c]+1dp[a+1][length[d]][d])dp[a+1][length[d]][d]=dp[a][c]+1;}}if(dp[a][c]best)best=dp[a][c];}fprintf(out,%d\n,best);return0;}解决背包问题动态规划的定义