环形DP学案.doc

怎样实现环形动态规划问题湖南省醴陵第一中学 曾妞妞 有些动态规划问题的模型是一个环形，比如，vijos上p1312的能量项链、p1218的数字游戏、usaco第一章中破碎的项链、rqnoj上p490的石子合并等问题。环形DP相对线性DP来说，难度增加了，对于环形DP这一类问题怎样解决？其基本的方法思想是怎样的？下面以NOIP2003提高组复赛的第二题数字游戏举例说明。【2003提高】数字游戏(Game)一、问题描述432-1丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共 n 个），你要按顺序将其分为 m 个部分，各部分内的数字相加，相加所得的 m 个结果对 10 取模后再相乘，最终得到一个数 k。游戏的要求是使你所得的 k 最大或者最小。例如，对于下面这圈数字（n=4，m=2）：当要求最小值时，(2-1) mod 10)(4+3) mod 10)=17=7，要求最大值时，为(2+4+3) mod 10)(-1 mod 10)=99=81。特别值得注意的是，无论是负数还是正数，对 10 取模的结果均为非负值。 丁丁请你编写程序帮他赢得这个游戏。【输入格式】 输入文件第一行有两个整数，n（1n50）和m（1m9）。以下n行每行有个整数，其绝对值不大于10，按顺序给出圈中的数字，首尾相接。 【输出格式】 输出文件有两行，各包含一个非负整数。第一行是程序得到的最小值，第二行是最大值。 【输入样例】 4 2 4 3 -1 2 【输出样例】7 81二、解题思路由于此题采用了环的设计，首先第一步肯定是针对环进行断链，第二步采用动态规划求出最优解。不同的断链方法就有不同的具体实现方法。对于环状，怎样破环成链呢？可以有两种处理方法：方法一：从环的不同位置切断就能得到不同的链，不同的链对应不同的起点结点，对不同的链分别进行DP，计算出各条链的最优解，最后从中选择一个最优解作为问题的最优解。 4-132比如，右图所示的4、3、2、-1这样一个环，根据切断位置的不同，可以有4种不同的切断法，即有4种不同的结点作为起点结点的链，如下所示：4 3 2 -13 2 -1 42 -1 4 3-1 4 3 2用DP分别对这4条链进行m部分的划分处理，每条链都能算出一个最大值和最小值，然后取这4个最大值和最小值中的最大值和最小值作为整个题目的最大值和最小值。 方法二：对于长度为n的环，任意选取一点为起点，由起点开始得到一条长度为n的链，将前面n-1长度的链复制并转移到链的末端，相当于将两条同样的链首尾相接。这样环的任意一种单向遍历方式都可以在这个长度为2n-1的链中实现。比如：4、3、2、-1这样一个环，在断链时，把3个数复制一次放到链的末尾就成了长度为7的链：4 3 2 -1 4 3 2，这样方法一中的环断链后形成的4条链在这条长度为7的链中都能实现，然后在这条长度为7的链上进行一次动态规划就可以求解出问题的解。三、具体实现。1、用方法一断链的程序实现及部分注释。此种方法的实现是通过n次动态规划分别计算出n条链的最优值program number;var fmin,fmax,sum:array0.50,0.50of longint;b,a:array0.50of longint;i,j,n,m:longint;max,min:int64;procedure doit;动态规划计算一条链分成m部分的最大值与最小值。var i,j,k:longint;begin filldword(fmin,sizeof(fmin)div 4,55555555); fillchar(fmax,sizeof(fmax), 0); for i:=1 to n do begin fmini,0:=sum1,i;fmaxi,0:=sum1,i;end; fmaxi,k表示前i个数切成m部分的最大值，k表示切的刀数 for k:=1 to m-1 do for i:=k+1 to n do for j:=1 to i-1 do begin if fmaxi,kfminj,k-1*sumj+1,i then fmini,k:=fminj,k-1*sumj+1,i; end;前i个数分成m部分等价于把前j个数分成m-1部分，从j+1到i分成1部分ij前i个数分成k部分前j个数分成k-1部分从j+1到i分成1部分 if fmaxn,m-1max then max:=fmaxn,m-1;记录最大值 if fminn,m-1min then min:=fminn,m-1; 记录最小值end;procedure makesum;计算任意两个数之间的数字相加的结果对 10 取模。 var i,j:longint; begin for i:=1 to n do for j:=i to n do sumi,j:=(sumi,j-1+aj)mod 10+10)mod 10; end;begin readln(n,m); max:=0;min:=maxlongint; for i:=1 to n do read(bi); for i:=1 to n do把环切断成n条链，根据切断位置的不同形成n条不同的链，枚举n个不同的结点作为起点结点时的最大值 begin fillchar(a,sizeof(a),0); fillchar(sum,sizeof(sum),0); for j:=1 to n do建立以i为起点结点的链 if i+j-1y then minn:=y else minn:=x;end;function maxn(x,y:longint):longint;begin if xy then maxn:=x else maxn:=y;end;begin read(n,m); for i:=1 to n do begin read(ai); an+i:=ai;把n个数复制一次放到链的末尾就成了长度为2 n的链 end; n:=n shl 1;链的长度变成2n for i:=1 to n do求出任意两个数之间的和 for j:=i to n do begin p:=0; for k:=i to j do p:=p+ak; p:=p mod 10; if p0 then p:=p+10; si,j:=p; end;for i:=1 to n do初始化 for j:=i to n do for k:=1 to m do begin fmini,j,k:=maxlongint; fmaxi,j,k:=-maxlongint; end; for i:=1 to n do初始化 for j:=i to n do begin fmini,j,1:=si,j; fmaxi,j,1:=si,j; end; for i:=1 to n do一次动态规划计算出任意两个数间划分成k部分的最小值fmini,j,k与最大值fmaxi,j,k for j:=i to n do for k:=2 to m do begin for p:=j-1 downto i do begin fmini,j,k:=minn(fmini,j,k,fmini,p,k-1*sp+1,j); fmaxi,j,k:=maxn(fmaxi,j,k,fmaxi,p,k-1*sp+1,j); end; end; fmini,j,k、fmaxi,j,k表示从i到j划分成k部分的最小值与最大值，从i到j分成k部分等价于从i到p分成k-1部分，从p+1到i分成1部分ij从i到j分成k部分p从i到p分成k-1部分从p+1到i分成1部分p+1 min:=maxlongint; max:=-maxlongint; n:=n shr 1; for i:=1 to n do求出各fmini,j,k的最小值，求出各fmaxi,j,k的最大值 begin min:=minn(min,fmini,i+n-1,m); max:=maxn(max,fmaxi,i+n-1,m); end; writeln(min); writeln(max);end.四、方法小结：以上两种方法的区别：用第一种方法断链，就要用n次动态规划才能求出最优值；用第二种方法断链，只要用1次动态规划就能算出最优值。同理可解决能量项链、数字游戏、破碎的项链、石子合并等问题了，去试试吧。五、动手编程：1、能量项链。在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为： (41)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 (41)2)3）=10*2*3+10*3*5+10*5*10=710。输入文件的第一行是一个正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当1iN时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出：最大能量。样例输入：42 3 5 10样例输出：7102、破碎的项链。你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3=N=350)，珠子是随意安排的。 这里是 n=29 的二个例子: 1 2 1 2 r b b r b r r b r b b b r r b r r r w r b r w w b b r r b b b b b b r b r r b r b r r r b r r r r r r b r b r r r w 图片 A 图片 B r 代表 红色的珠子 b 代表 蓝色的珠子 w 代表 白色的珠子第一和第二个珠子在图片中已经被作记号。图片 A 中的项链可以用下面的字符串表示：brbrrrbbbrrrrrbrrbbrbbbbrrrrb .假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事。(颜色可能与在这之前收集的不同) 确定应该在哪里打破项链来收集到最大多数的数目的子。 Example 举例来说，在图片 A 中的项链，可以收集到8个珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链。 在一些项链中，包括白色的珠子如图片 B 所示。 当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。 表现项链的字符串将会包括三符号