搜索
#本资料非原创，为了方便大家复习，特此整理。在此感谢提供试题的作者专题一：动态规划1.结点选择问题描述有一棵n个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？解题思路：这题模型是树形动态规划入门题目，dp[i][0]表示该节点不被选择，dp[i][1]表示该结点被选择。转移方程为:dp[u][1]+=dp[v][0];//选择了u结点，则与它邻接的结点不选；dp[u][0]+=max(dp[v][0]，dp[v][1]);不选择u结点，则与它邻接的结点选择结果最大的；应该特别注意：该题结点数量较大，应该选用邻接表存储边的关系1.#includecstdio2.#includecstring3.#definemax(a,b)((a)(b)?(a):(b))4.#definemaxn1000105.boolvis[maxn];6.intdp[maxn][2];7.intfather[maxn];8.inthead[maxn];9.intn;10.intcnt;11.structEdge12.{13.intto,next;14.}edge[2*maxn];15.voidadd(intu,intv)16.{17.edge[cnt].to=v;18.edge[cnt].next=head[u];19.head[u]=cnt++;20.}21.voidtreedp(intu)22.{23.vis[u]=1;24.for(inti=head[u];i!=-1;i=edge[i].next)25.{26.intv=edge[i].to;27.if(!vis[v])28.{29.treedp(v);30.dp[u][1]+=dp[v][0];31.dp[u][0]+=max(dp[v][1],dp[v][0]);32.}33.}34.}35.voidinit()36.{37.cnt=0;38.memset(dp,0,sizeof(dp));39.memset(father,0,sizeof(father));40.memset(vis,0,sizeof(vis));41.memset(head,-1,sizeof(head));42.}43.intmain()44.{45.init();46.scanf(%d,&n);47.for(inti=1;i=n;i++)48.scanf(%d,&dp[i][1]);49.introot=0;50.intbegin=1;51.for(inti=0;in-1;i++)52.{53.inta,b;54.scanf(%d%d,&a,&b);55.add(a,b);56.add(b,a);57.father[b]=a;58.if(root==b||begin)59.{60.root=a;61.}62.}63.64.while(father[root])65.root=father[root];66.treedp(root);67.intans;68.ans=max(dp[root][0],dp[root][1]);69.printf(%d\n,ans);70.}2.K好数问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K=4，L=2的时候，所有K好数为11、13、20、22、30、31、33共7个。由于这个数目很大，请你输出它对1000000007取模后的值。解题思路：dp[i][j]表示第i位为j的时候的个I好数个数；因此有转移方程：dp[i][j]=dp[i-1][m]+dp[i][j];m为上一位的值，满足的条件应为m-j的绝对值不为1.即不相邻；应当注意的是：最后在求和的时候不能简单的统计dp[l][m]0=mk;因为首位如果是0的话，其实不足L位了，所以0mk,也许有人会疑问这是不统计L位的0，不是第一位呀。。。。。。其实仔细想想，是等效的。1.#includecstdio2.#includecstring3.#definemod10000000074.#defineabs(a,b)((a)(b)?(a-b):(b-a))5.intdp[110][110];6.intmain()7.{8.intk,l;9.memset(dp,0,sizeof(dp));10.scanf(%d%d,&k,&l);11.for(inti=0;ik;i++)12.dp[1][i]=1;13.for(inti=2;i=l;i++)14.{15.for(intj=0;jk;j++)16.{17.for(intm=0;mk;m++)18.{19.if(abs(m,j)!=1)20.dp[i][j]=(dp[i][j]%mod+dp[i-1][m]%mod)%mod;21.}22.}23.}24.intans=0;25.for(inti=1;ik;i++)26.ans=(ans%mod+dp[l][i]%mod)%mod;27.printf(%d\n,ans);28.}3.导弹拦截-动态规划问题描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。解题思路：因为要求后面每一发炮弹都不能高于前一发，故问题就转化成了求最长不下降子序列，用n^2算法即可。对于第二问，遇到高于前一项的，便要准备另外一套系统，而且要全部拦截，故求严格的最长上升子序列。dp[i]表示以i位置结束的最长不下降子序列；dps[i]表示以i位置结束的最长上升子序列；注意初始化问题，对于每一个dp[i]，最少也会包括自身，所以都要初始化为1；[cpp]viewplaincopy1.#includecstdio2.#includecstring3.#includealgorithm4.#definemax(a,b)((a)(b)?(a):(b))5.usingnamespacestd;6.intmain()7.{8.intdp[10010];9.intdps[10010];10.memset(dp,0,sizeof(dp));11.memset(dps,0,sizeof(dps));12.intn=0;13.intnum[10010];14.intx;15.while(~scanf(%d,&x))16.num[++n]=x;17.for(inti=1;i=n;i++)18.dp[i]=dps[i]=1;19.for(inti=1;i=n;i++)20.{21.for(intj=1;ji;j++)22.{23.if(num[i]=num[j])24.{25.dp[i]=max(dp[i],dp[j]+1);26.}27.if(num[i]num[j])28.{29.dps[i]=max(dps[i],dps[j]+1);30.}31.}32.}33.intans1=0,ans2=0;34.for(inti=1;i=n;i++)35.{36.ans1=max(ans1,dp[i]);37.ans2=max(ans2,dps[i]);38.}39.printf(%d\n,ans1);40.printf(%d\n,ans2);41.}4.乘积最大问题描述今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：3*12=3631*2=62这时，符合题目要求的结果是：31*2=62现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。输入格式程序的输入共有两行：第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）第二行是一个长度为N的数字串。解题思路：动态规划的经典题目。i从0开始；ans[i][j]表示长度为i+1的数字串插入j个*号能够获得的最大的乘积；ans[i][0]显然是长度为i+1的数字串所对应的数字；状态转移方程：利用最优子结构的性质，如果在k个字符后插入第j个*取得最大值，则ans[k][j-1]也是最大，因此只需要在确定i,j的情况下，只需要枚举最后一个*号的位置即可ans[i][j]=max(ans[i][j],ans[k][j-1]*(k+1个位置起，i-k个长度字符串所对应的数字)；0=ki;1=j=min(i,*最大的个数)；[cpp]viewplaincopy1.#includecstdio2.#includecstring3.#includeiostream4.#includestring5.#includealgorithm6.usingnamespacestd;7.intchange(stringa)8.{9.intans=a[0]-'0';10.intlen=a.length();11.for(inti=1;ilen;i++)12.{13.ans=ans*10+a[i]-'0';14.}15.returnans;16.}17.intmain()18.{19.intm,n;20.cinmn;21.strings;22.cins;23.longlongans[45][7];24.memset(ans,0,sizeof(ans));25.for(inti=1;i=m;i++)26.ans[i-1][0]=change(s.substr(0,i));27.28.for(inti=0;im;i++)29.{30.intt=min(i,n);31.for(intj=1;j=t;j++)32.{33.for(intk=0;ki;k++)34.{35.longlongtt=change(s.substr(k+1,i-k));36.ans[i][j]=max(ans[i][j],ans[k][j-1]*tt);37.}38.}39.}40.coutans[m-1][n];41.}5.数的划分问题描述将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法。输入格式n，k输出格式一个整数，即不同的分法样例输入73样例输出4{四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}解题思路：dp[n][k]表示把划分为k个数的方案种数；有俩种情况，不包含1：则可以先找出k个1放在每一份中，然后把剩下的n-k分成k份即可；包含1：则先把1拿出来当做单独的一份，则把n-1划分成k-1份即可；状态转移方程为：dp[i][j]=dp[i-j][j]+dp[i-1][j-1];ijdp[i][j]=1;i=jdp[i][j]=0;ij[cpp]viewplaincopy1.#includecstdio2.#includecstring3.intmain()4.{5.intn,k;6.scanf(%d%d,&n,&k);7.longlongdp[2