【例题2】乘积最大1262 Description
今年是国际数学联盟确定的“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设计一个程序，求得正确的答案。 Input
程序的输入共有两行:
第一行共有2个自然数N,K (6<=N<=40，1<=K<=6) 第二行是一个K度为N的数字串。 Output
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 Sample Input 4 2 1231
Sample Output 62 【算法分析】 2、 阶段和状态：
sum[i][j]：表示在s串中从i开始到j结束的数值； f[i][j]：表示前i个字符中插入j各乘号所得的最大乘积； 2、状态转移方程：
初始化：f[i][0]=sum[1][i]; 状
态
转
移
方
程
：
f[i][j]=max{f[t][j-1]*sum[t+1][i]}(1<=j<=k,j+1<=i<=n,j<=t<=i-1)
answer=f[n][k]
3、核心子程序： int g(int a[],int bg,int ed) { int i,s=0; for(i=bg;i<=ed;i++)s=s*10+a[i]; return s; } int main() { int n,k,m,t,a[41],i,j,l,f[41][8]={0},sum[16][16]; char c; cin>>n>>k; //n个数，k个乘号
for(i=1;i<=n;i++){cin>>c;a[i]=c-‘0’;} //转换为数值 for(i=1;i<=n;i++) for(j=i;j<=n;j++)sum[i][j]=g(a,i,j); for(i=1;i<=n;i++)f[i][0]=sum[1][i]; //初始化 for(j=1;j<=k;j++) //乘号数目 for(i=j+1;i<=n;i++) //数字个数 { m=0; for(t=j;t<=i-1;t++) //决策前t个数字中添加j-1个乘号 if(m 二、复制书稿 Description 假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。任务是将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。 意思是说，存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m，这样，第I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的，并且每个抄写员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，输出结果排序最小的一种） Input 第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.(m<100) Output 共k行。每行两个整数：第I行表示第I抄写员抄的书本编号起止。 Sample Input 9 3 1 2 3 4 5 6 7 8 9 Sample Output 1 5 6 7 8 9 【算法分析】 该题中 M 本书是顺序排列的，K 个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到K<=M，以抄写员编号来划分阶段会方便些。 设 F（I，J）为前 I 个抄写员复制前 J 本书的最小“页数最大数”。于是便有 F（I，J）=MIN{ F（I-1，V），T（V+1，J）} （1<=I<=K，I<=J<=M-K+I，I-1<=V<=J-1）。 其中 T（V+1，J）表示从第 V+1 本书到第 J 本书的页数和。边界条件 F（1,i）=T(1,j)。 题目类别：资源划分类 #include void out(int i,int j) { if(i==0) return; out(i-1,b[i][j]-1); cout< int n,k,i,j,p,max,f[100][100],min,mp,x; cin>>n>>k; a[0]=0; for(i=1;i<=n;i++){ cin>>x;a[i]=a[i]+x;}//a[i]表示前i本书的页数累加和 for(i=1;i<=n;i++) {f[1][i]=a[i];b[1][i]=1;} for(i=0;i<=k;i++) f[i][0]=0; for(i=2;i<=k;i++) for(j=1;j<=n-k+i;j++) { f[i][j]=200000; for(p=i;p<=j;p++)//枚举第i个人抄的书的范围i?j { max=Max(f[i-1][p-1],a[j]-a[p-1]); if(f[i][j]>max) { f[i][j]=max; b[i][j]=p;//前j本书由i个人抄时第i个人抄的第一本书编号为p } } } out(k,n); return 0; } 思考： 二分答案 【2001提高】统计单词个数1258 Description：给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(k小于等于40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。 Input： 第一行有二个正整数(p，k),p表示字串的行数;,k表示分为k个部分。 接下来的p行，每行均有20个字符。 再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6) 接下来的s行，每行均有一个单词。 Output ：结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。 Sample Input 1 3 thisisabookyouareaoh 4 is a ok sab Sample Output：7 Hint：this/isabookyoua/reaoh 动归，题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置 i的参数mlen[i]表示以位置i的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词。这样对于所有的不同l个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的mlen的值，这一部分的复杂度为O(wl2)。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分，故我们类比其他的分割字串的问题，列出动态规划的方程如下： f[l,k]?max?f[l?i,k?1]?g[l?i?1,i]? 1?i?l?1这里有初值f[l,1]为： f[l,1]?g[1,l] 这个式子中，f[l,k]表示把字串前l个字符分成k段时所形成的最多单词的数目， g[p,i]由于过于庞大，不能用预计算的方法加快速度，只能现用现算。计算的方法为对于所有 p?q?p?i?1的q， 如果mlen[q]存在（也就是有单词可以在位置q匹配上），且q单词。把所有这样位置的数目加起来就可以得到 ?mlen[q]?1?p?i?1，则该位置必然可以匹配上一个 g[p,i]的值了。这样算法的复杂度为O(kl3)。 f的值。这样在i由i'增加到il增加，i增加的顺序计算但这里计算还有一个技巧，就是我们可以依次按照k增加， 的时候，由于在计算i'?1'?1所对应的g值时可以用 g[p?1,i'?1]?g[p,i']?1p?1?mlen[p?1]?1?p?i'?1 ?g[p,i']p?1?mlen[p?1]?1?p?i'?1这个方程进行复杂度为O(1)的递推计算，故总复杂度可以降到O(kl2+wl2)。这种被称作双重动态规划的方法，请读者自己好好体会。 #include 文件排版（format） Description 写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。 完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子： **************************** This is the example you are actually considering. 假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果： **************************** This is the example you are actually considering. 但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词“are”移到下一行我们将得到较好的结果： **************************** This is the example you are actually considering. 当然，这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度，一个包含N个空格符的空白段，其难看程度值为(n-1)^2，程序的目的是使难看程度的总和最小化。例如，第一个例子的难看程度是1+7*7=50，而第二个例子的难看程度仅为1+1+1+4+1+4=12。 输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输出，此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500，当然在这种情况下，该行的实际长度即为该单词的长度。 Input 输入文件第一行是一个整数N，表示该段要求达到的宽度，1<=N<=80。该段文章由一个或多个单词组成，单词由ASCII码值为33到126（包含33和126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过10000个字符，任何一行都不会超过100个字符，任何一个单词都在同一行内。 Output 对于每个段落，找出使其难看程度最小的排版形式并输出句子：“Minimal badness is B.”，B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。 Sample Input 28 This is the example you are actually considering. Sample Output Minimal badness is 12. 思考： 筷子、乐队，邮局局问题、花的美学价值 合并类型DP(分治) 特点：一个大问题可由多个规模小的同类问题组合求解 【例题1】：最小代价子母树（石子归并问题）1119 Description 设有n堆石子排成一排，其编号为1、2、3、?、n（n<=100）。每堆石子的数量用：a[1]、a[2]、?、a[n] 表示，现将这n堆石子归并成一堆，归并的规则： ◆每次只能将相邻两堆归并成一堆，即：第 1 堆石子 a[1] 只能与第 2 堆石子 a[2] 归并，最后一堆石子 a[n] 只能与 a[n-1] 归并，中间的石子 a[i] 只能与 a[i-1] 或 a[i+1] 归并； ◆每次归并的代价是两堆石子的重量之和。 例如：假设有这样7堆石子，各堆石子的数量分别是：13 7 8 16 21 4 18，将它们归并成一堆有多种归并方法，下图表示了其中两种归并方法：