动态规划程序设计5.doc

《动态规划程序设计5.doc》由会员分享，可在线阅读，更多相关《动态规划程序设计5.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、安阳一中信息学奥赛辅导资料第 1 页 共 6 页动态规划程序设计动态规划程序设计 5区间型动态规划在信息学竞赛中应用甚广，它是动态规划中的经典问题，最小代价字母树是这 类动态规划最经典的体现，对于初学者而言这类动态规划并不太好理解。于是，区间型动态规划又 成了动态规划中的难点问题。*历届大赛中区间型动态规划题目的考查。区间型动态规划是各大信息学竞赛出题的热点，具体体现在以下题目：1合并石子NOI l9952能量项链NOIP 20063加分二叉树NOIP 20034最优排序二又树ctsc 96 这些题目出现的频次及其所在比赛的重要性足以说明区间型动态规划在各类动态规划中有着举 足轻重的地位。 区

2、间类模型的动态规划,一般是要求整段区间的最优值,子问题一般是把区间分成两个子区间。一 般用二维数组表示状态,例如 fi,j表示从 i 到 j 的最优值,则状态转移方程就是跟子区间之间的关系。一、区间型动态规划的算法分析一、区间型动态规划的算法分析在这里就以经典的最小代价字母树作为例子，对区间型动态规划的算法进行分析。问题描述：给定一个序列，如 4，1，2，3，我们将它们相加进行合并，最终合并成一个数，每次相加的 代价是两个加数的和，求怎样的相加顺序可以使总代价最小。很多初学者认为这类动态规划不易理解，其重要原因是这类动态规划与其他动态规划的思想不 大相同，而初学者又是利用其他动态规划的思想来解

3、决这类动态规划，从而进入了思维误区。这种 错误的思维模式一旦建立便很难重新建立正确的解题思想，从而陷入绝境。这类动态规划正确的解法是这样的：首先，根据动态规划无后效性的性质可以想到：对于一个序列：A1，A2,An，假如最后相加 的两个数是第一个数到第 i 个数的和 s1i以及第 i+1 个数到第 n 个数的和 si+1n，另外， 对于第一个数到第 i 个数相加的最小代价是 Fl，i以及从第 i+1 到第 n 个数相加的最小代价为 Fi+1，n，则总代价即为 Fi+1，n+F1，i(前面相加的最小代价)+s1i+si+1n(最后一 次相加的最小代价)。由此，我们可以清楚地看出要想求出总代价的最小

4、值只要枚举 i 的位置，使 得 Fi+1，n+F1，i+S1-i+si+1n的和最小即可。综上所述，我们可以总结出状态转移方 程：Fi，J：=rainFi，k+Fk+1，j+Si，k+Sk+1，j)状态转移数组 F 即代表从第 i 个数到第 j 个数相加的最小代价，s 数组为预处理好的从第 i 个数 到第 j 个数的和。核心代码如下：For i：=1 to n doFor j：=1 to n-I doFor k：=j to i+j-1 doIf fj,i+jfj,k+fk+1,I+j+sj,k+sk+1,I+j安阳一中信息学奥赛辅导资料第 2 页 共 6 页Then fj,I+j= fj,k+

5、fk+1,I+j+sj,k+sk+1,I+j 最小值 ANS 为 F1，n。二、区间型动态规划的具体应用二、区间型动态规划的具体应用例例 1：问题描述 给定一个具有 N(Nb then min:=b else min:=a; end; procedure digui(x,y:longint); beginif dgx,y=0 then exit;安阳一中信息学奥赛辅导资料第 3 页 共 6 页digui(x,dgx,y);digui(dgx,y,y);if bj thenbeginwrite(x, ,dgx,y, ,y);bj:=false;endelsewrite(, ,x, ,dgx,y,

6、 ,y); end; beginreadln(n);for i:=1 to n dobeginread(Si);end;readln;fillchar(f,sizeof(f),$7f);fillchar(dg,sizeof(dg),0);for i:=1 to n dofi,i+1:=0; /数据赋初值for jj:=2 to n-1 do /枚举多边形边数for i:=1 to n-1 do /枚举起点beginif i+jjn then break;j:=i+jj;for k:=i+1 to j-1 dobegintt:=fi,k+fk,j+si*sj*sk;/DP 转移方程if fi,j

7、tt thenbeginfi,j:=tt;dgi,j:=k; /记录中间点，以便输出划分方法end;end;end;writeln(f1,n);bj:=true;digui(1,n);writeln; end.安阳一中信息学奥赛辅导资料第 4 页 共 6 页例例 2石子归并石子归并题目描述：在一个圆形操场的四周摆放着 N 堆石子(Nl00)，现要将石子有次序地合并成一堆。规定每次 只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。编一程序， 由文件读入堆栈数 N 及每堆栈的石子数(20)。(1)选择一种合并石子的方案，使用权得做 N-1 次合并，得分的总和最小：(2)

8、选择一种合并石子的方案，使用权得做 N-1 次合并，得分的总和最大。输入数据：第一行为石子堆数 N：第二行为每堆的石子数，每两个数之间用一个空格分隔。输出数据：从第一至第 N 行为得分最小的合并方案。第 N+I 行是空行。从第 N+2 行到第 2N+1 行是得分最 大的合并方案。每种合并方案用 N 行表示，其中第 i 行(1iN)表示第 i 次合并前各堆的石子数 (依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。输入输出范例：输入：44 5 9 4输出：-4 5 9 -4-8 -5 9-1 3 -9224 -5 -9 44 14 -4-4 -1 822这道题目可

9、以说跟最小代价字母树只有两个不同的地方，一个是所求序列是一个环形的，另一 个是要求输出方案。对于输出方案而言，只需要用一般动态规划记录方案的方法即可，因为不是本 文的重点在此就不再深究。对于所求序列是环形的问题其实只需要用一个小小的技巧便轻松解决， 请先看代码： /预处理 Read(n)：For I:=1 to n doBeginRead(aI)a i+n : =a i ; End; For i:=l to n do For j:=l to n doFor k:=i to j doSI, j: =SI, j+a k;安阳一中信息学奥赛辅导资料第 5 页 共 6 页/DP 过程For i:=1

10、to n do For j:=l to 2*n-I doFor k:=j to i+j-1 do If Fj, i+jFj, k+Fk+l, i+j+S j, k+Sk+l, i+jthen Fj, i+j: =Fj, k+Fk+l, i+j+Sj, k+Sk+l, i+j; For i:=1 to n-1 doAns: =minFi, i+n-1 最小值为 Ans从代码中可以看出，这道题的写法跟最小代价字母树的区别在于权举起点的时候长度增加到了 2*n，并且在最后求解的时候也需要枚举起点，求长度为 n 的最小值，这恰恰是利用了区间型动态 规划的特点。当然，在读入数据的时候需要把初始数组的长度

11、扩大一倍然后再进行预处理即可。这 种方法在能量项链一题中还有具体的体现，因为能量项链的核心算法与本题几乎一样，所以就不再 赘述。大家可以自己练习。例例 3加分二叉树加分二叉树【问题描述】设一个 n 个结点的二叉树 tree 的中序遍历为(1，2，3，13)，其中数字 l，2，3，n 为 界点编号。每个结点都有一个分数(均为正整数)，记第 j 个结点的分数为 di，tree 及它的每个子 树都有一个加分，任一棵子树 subrtee(也包含 tree 本身)的加分计算方法如下：subtree 的左子树的加分 subtree 的右子树的加分+subtree 的根的分数若某个子树为空，规定其加分为 l

12、，叶子的加分就是叶结点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为(1，2，3，n)且加分最高的二叉树 tree。要求输出：(1)tree 的最高加分(2)tree 的前序遍历【输入格式】第 1 行：一个整数 n(n30)，为节点个数。第 2 行：n 个用空格隔开的整数，为每个节点的分数(分数100)。【输出格式】第 1 行：一个整数，为最高加分(结果不会超过 4，000，000，000)。第 2 行：rl 个用空格隔开的整数，为该树的前序遍历。【输入样例】55 7 1 2 1 0【输出样例】1453 1 2 4 5这道题目巧妙地将区间型动态规划和二叉树相结合，既考查了二叉树的基本性质

13、，又考查了大 家对动态规划的掌握，不得不承认这是一道经典好题。同样，这道题最后要求输出前序遍历，只需 要用递归建树即可，这里就不多说了。具体的预处理过程和动态规划过程如下： /预处理read (n) ; For i: =1 to n do安阳一中信息学奥赛辅导资料第 6 页 共 6 页read (a i) ; For i:=0 to n doFor j:=0 to n do Fi, j: =1; For i:=l to n do Fi, i:=ai; /DP 过程For i:=2 to n doFor j:=l to n-i+l doFor k:=j to i+j-1 doif fj, i+j-1fj,k-1*fk+1, i+j-1+akthen fj,i+j-1:=fj,k-1*fk+l,i+j-1+ak;其中 Ak是读入的数组，F1，n同样为最终结果，表示从第一个到第 n 个数进行建树的最大 价值。 小结：对于区间型动态规划的思想和具体的应用就是这些，其实这类动态规划并不难，关键在 于领悟区间的含义，更重要的是将这种思想进行变通，灵活应用。另外，在程序的实现过程中掌握 一些技巧也是必需的，这是轻松解题的关键，最后希望大家能够通过此文轻松掌握区间型动态规划。