第9章第4节动态规划经典题(C++版).

第九章动态规划第一节动态规划的基本模型第二节动态规划与递推第三节背包问题第四节动态规划经典题动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。第四节动态规划经典题【例9-18】、合并石子【问题描述】在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。【编程任务】试设计一个程序，计算出将Ｎ堆石子合并成一堆的最小得分。【输入格式】第一行为一个正整数N(2≤Ｎ≤100)；以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。【输出格式】为一个正整数，即最小得分。s[i]表示前i堆石头的价值总和，f[i][j]表示把第i堆到第j堆的石头合并成一堆的最优值。for(i=n-1;i=1;i--)for(j=i+1;j=n;j++)for(k=i;k=j-1;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);输出f[1][n]【输入样例】713781621418【输出样例】239【参考程序】#includecstdio#includecstringintmin(inta,intb){returnab?b:a;//三目运算符，相当于if(ab)returnb;elsereturna;}intf[101][101];ints[101];intn,i,j,k,x;intmain(){scanf(%d,&n);for(i=1;i=n;i++){scanf(%d,&x);s[i]=s[i-1]+x;}memset(f,127/3,sizeof(f));//赋值127是很大的正数，若无/3后面的相加for(i=1;i=n;i++)f[i][i]=0;//可能超出int的范围for(i=n-1;i=1;i--)for(j=i+1;j=n;j++)for(k=i;k=j-1;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);printf(%d\n,f[1][n]);return0;}【例9-19】乘积最大【问题描述】今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：1）3*12=362）31*2=62这时，符合题目要求的结果是：31*2=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。【输入格式】mul.in第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）第二行是一个长度为N的数字串。【输出格式】mul.out输出所求得的最大乘积（一个自然数）。【输入样例】421231【输出样例】62【算法分析】此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i][k]表示在前i位数中插入K个乘号所得的最大值，a[j][i]表示从第j位到第i位所组成的自然数。用f[i][k]存储阶段K的每一个状态，可以得状态转移方程：f[i][k]=max{f[j][k-1]*a[j+1][i]}（k=j=i）边界值：f[j][0]=a[1][j](1j=i)根据状态转移方程，我们就很容易写出动态规划程序：for(k=1;k=r;k++)//r为乘号个数for(i=k+1;i=n;i++)for(j=k;ji;j++)if(f[i][k]f[j][k-1]*a[j+1][i])f[i][k]=f[j][k-1]*a[j+1][i]【参考程序】#includecstdiolonglonga[11][11],f[11][11];longlongs;intn,i,k,k1,j;intmax(inta,intb){returnab?a:b;}intmain(){scanf(%d%d,&n,&k1);scanf(%lld,&s);for(i=n;i=1;i--){a[i][i]=s%10;s/=10;}for(i=2;i=n;i++)for(j=i-1;j=1;j--)a[j][i]=a[j][i-1]*10+a[i][i];for(i=1;i=n;i++)//预处理不加乘号的情况f[i][0]=a[1][i];for(k=1;k=k1;k++)for(i=k+1;i=n;i++)for(j=k;ji;j++)f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);printf(%lld\n,f[n][k1]);return0;}【例9-20】编辑距离【问题描述】设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：1、删除一个字符；2、插入一个字符；3、将一个字符改为另一个字符。【编程任务】对任的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。【输入格式】edit.in第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。【输出格式】edit.out只有一个正整数，为最少字符操作次数。【输入样例】sfdqxbwgfdgw【输出样例】4【算法分析】状态：f[i][j]记录ai与bj的最优编辑距离结果：f[m][n]，其中m、n分别是a、b的串长初值：b串空，要删a串长个字符；a串空，要插b串长个字符转移方程：当a[i]=b[j]时，f[i][j]=f[i-1][j-1]，否则，f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1)说明：f[i-1][j-1]+1：改a[i]为b[j]；f[i][j-1]+1：a[i]后插入b[j-1]；f[i-1][j]+1：删a[i]。【参考程序】#includecstdio#includecstringintmin(inta,intb){returnab?a:b;}intf[202][202];chars1[202],s2[202];inti,j,k,m,n;intmain(){scanf(%s%s,s1,s2);m=strlen(s1);n=strlen(s2);for(i=1;i=m;i++)f[i][0]=i;//到i位置为止把字符串A的内容全部删除for(i=1;i=n;i++)f[0][i]=i;//在开头给字符串A添上和B到i位置相同的字符for(i=1;i=m;i++)for(j=1;j=n;j++)if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1];elsef[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;printf(%d\n,f[m][n]);return0;}【例9-21】方格取数【问题描述】设有N×N的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：某人从图中的左上角的A出发，可以向下行走，也可以向右行走，直到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。【编程任务】此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。【输入格式】Pane.in输入文件Pane.in第一行为一个整数N（N≤10），表示N×N的方格图。接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。一行000表示结束。【输出格式】Pane.out输出文件Pane.out包含一个整数，表示两条路径上取得的最大的和。【输入样例】823132663574414522156463157214000【输出样例】67【算法分析】一个四重循环枚举两条路分别走到的位置。由于每个点均从上或左继承而来，故内部有四个if，分别表示两个点从上上、上左、左上、左左继承来时，加上当前两个点所取得的最大值。a[i][j]表示(i,j)格上的值，sum[i][j][h][k]表示第一条路走到(i,j)，第二条路走到(h,k)时的最优解。例如，sum[i][j][h][k]=max{sum[i][j][h][k],sum[i-1][j][h-1][k]+a[i][j]+a[h][k]}，表示两点均从上面位置走来。当(i,j)(h,k)）时sum[i][j][h][k]:=max{sum[i-1][j][h-1][k],sum[i][j-1][h][k-1],sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]}+a[i][j]+a[h][k];当(i,j)=(h,k)时sum[i][j][h][k]:=max{sum[i-1][j][h-1][k],sum[i][j-1][h][k-1],sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]}+a[i][j];【参考程序1】#includecstdiointmax(inta,intb){returnab?a:b;}inta[51][51];intsum[51][51][51][51];intn,i,j,h,k,x,y,z;intmain(){scanf(%d%d%d%d,&n,&x,&y,&z);while(x&&y&&z)//C++中大于0的正整数都看作true，只有0看作false{a[x][y]=z;scanf(%d%d%d,&x,&y,&z);}for(i=1;i=n;i++)for(j=1;j=n;j++)for(h=1;h=n;h++)for(k=1;k=n;k++){inttmp1=max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]);inttmp2=max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]);sum[i][j][h][k]=max(tmp1,tmp2)+a[i][j];if(i!=h&&j!=k)sum[i][j][h][k]+=a[h][k];}printf(%d\n,sum[n][n][n][n]);return0;}【例9-22】低价购买(buylow)【问题描述】“低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的购买建议:“低价