下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 区间动规

区间动规.doc

区间动规

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《区间动规doc》,可适用于工程科技领域

安阳一中信息学奥赛辅导资料区间动规专题区间型动态规划在信息学竞赛中应用甚广它是动态规划中的经典问题最小代价字母树是这类动态规划最经典的体现对于初学者而言这类动态规划并不太好理解。于是区间型动态规划又成了动态规划中的难点问题。*历届大赛中区间型动态规划题目的考查。区间型动态规划是各大信息学竞赛出题的热点具体体现在以下题目:.合并石子NOIl.能量项链NOIP.加分二叉树NOIP.最优排序二又树ctsc这些题目出现的频次及其所在比赛的重要性足以说明区间型动态规划在各类动态规划中有着举足轻重的地位。区间类模型的动态规划,一般是要求整段区间的最优值,子问题一般是把区间分成两个子区间。一般用二维数组表示状态,例如fi,j表示从i到j的最优值,则状态转移方程就是跟子区间之间的关系。一、区间型动态规划的算法分析在这里就以经典的最小代价字母树作为例子对区间型动态规划的算法进行分析。问题描述:给定一个序列如我们将它们相加进行合并最终合并成一个数每次相加的代价是两个加数的和求怎样的相加顺序可以使总代价最小。很多初学者认为这类动态规划不易理解其重要原因是这类动态规划与其他动态规划的思想不大相同而初学者又是利用其他动态规划的思想来解决这类动态规划从而进入了思维误区。这种错误的思维模式一旦建立便很难重新建立正确的解题思想从而陷入绝境。这类动态规划正确的解法是这样的:首先根据动态规划无后效性的性质可以想到:对于一个序列:AA,…An假如最后相加的两个数是第一个数到第i个数的和s……i以及第i个数到第n个数的和si…n另外对于第一个数到第i个数相加的最小代价是Fli以及从第i到第n个数相加的最小代价为Fin则总代价即为FinFi(前面相加的最小代价)s…isi…n(最后一次相加的最小代价)。由此我们可以清楚地看出要想求出总代价的最小值只要枚举i的位置使得FinFiSisi…n的和最小即可。综上所述我们可以总结出状态转移方程:FiJ:=rain{FikFkjSikSkj)状态转移数组F即代表从第i个数到第j个数相加的最小代价s数组为预处理好的从第i个数到第j个数的和。核心代码如下:Fori:=tondoForj:=tonIdoFork:=jtoijdoIffj,ij>fj,kfk,Ijsj,ksk,IjThenfj,Ij=fj,kfk,Ijsj,ksk,Ij最小值ANS为Fn。二、区间型动态规划的具体应用例:问题描述给定一个具有N(N<)个顶点(从到N编号)的凸多边形,每个顶点的权均已知。问如何把这个凸多边形划分成N个互不相交的三角形,使得这些三角形顶点的权的乘积之和最小输入文件:第一行顶点数N第二行N个顶点(从到N)的权值输出格式:最小的和的值各三角形组成的方式输入示例:输出示例:Theminimumis:Theformationoftriangle:,,题目解析这是一道很典型的区间类型动态规划问题。设FI,J(I<J)表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积,我们可以得到下面的动态转移方程:FI,J=Min{FI,KFK,JSI*SJ*SK)(I<K<J)目标状态为:F,N但我们可以发现,由于这里为乘积之和,在输入数据较大时有可能超过长整形甚至实形的范围,所以我们还需用高精度计算。但这是大家的基本功,程序中没有写,请读者自行完成。参考程序:vari,j,k,l,m,n,jj:longinttt:ints:arrayoflongintbj:booleanf:array,ofintdg:array,oflongintfunctionmin(a,b:longint):longintbeginifa>bthenmin:=belsemin:=aendproceduredigui(x,y:longint)beginifdgx,y=thenexitdigui(x,dgx,y)digui(dgx,y,y)ifbjthenbeginwrite(x,'',dgx,y,'',y)bj:=falseendelsewrite(',',x,'',dgx,y,'',y)endbeginreadln(n)fori:=tondobeginread(Si)endreadlnfillchar(f,sizeof(f),$f)fillchar(dg,sizeof(dg),)fori:=tondofi,i:=数据赋初值forjj:=tondo枚举多边形边数fori:=tondo枚举起点beginifijj>nthenbreakj:=ijjfork:=itojdobegintt:=fi,kfk,jsi*sj*skDP转移方程iffi,j>ttthenbeginfi,j:=ttdgi,j:=k记录中间点以便输出划分方法endendendwriteln(f,n)bj:=truedigui(,n)writelnend例.石子归并题目描述:在一个圆形操场的四周摆放着N堆石子(N≤l)现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆并将新的一堆的石子数记为该次合并的得分。编一程序由文件读入堆栈数N及每堆栈的石子数(≤)。()选择一种合并石子的方案使用权得做N次合并得分的总和最小:()选择一种合并石子的方案使用权得做N次合并得分的总和最大。输入数据:第一行为石子堆数N:第二行为每堆的石子数每两个数之间用一个空格分隔。输出数据:从第一至第N行为得分最小的合并方案。第NI行是空行。从第N行到第N行是得分最大的合并方案。每种合并方案用N行表示其中第i行(≤i≤N)表示第i次合并前各堆的石子数(依顺时针次序输出哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。输入输出范例:输入:输出:–这道题目可以说跟最小代价字母树只有两个不同的地方一个是所求序列是一个环形的另一个是要求输出方案。对于输出方案而言只需要用一般动态规划记录方案的方法即可因为不是本文的重点在此就不再深究。对于所求序列是环形的问题其实只需要用一个小小的技巧便轻松解决请先看代码:预处理Read(n):ForI:=tondoBeginRead(aI)ain:=aiEndFori:=ltondoForj:=ltondoFork:=itojdoSI,j:=SI,jakDP过程Fori:=tondoForj:=lto*nIdoFork:=jtoijdoIfFj,ij>Fj,kFkl,ijSj,kSkl,ijthenFj,ij:=Fj,kFkl,ijSj,kSkl,ijFori:=tondoAns:=min{Fi,in}最小值为Ans从代码中可以看出这道题的写法跟最小代价字母树的区别在于权举起点的时候长度增加到了*n并且在最后求解的时候也需要枚举起点求长度为n的最小值这恰恰是利用了区间型动态规划的特点。当然在读入数据的时候需要把初始数组的长度扩大一倍然后再进行预处理即可。这种方法在能量项链一题中还有具体的体现因为能量项链的核心算法与本题几乎一样所以就不再赘述。大家可以自己练习。例.加分二叉树【问题描述】设一个n个结点的二叉树tree的中序遍历为(…)其中数字l…n为界点编号。每个结点都有一个分数(均为正整数)记第j个结点的分数为ditree及它的每个子树都有一个加分任一棵子树subrtee(也包含tree本身)的加分计算方法如下:subtree的左子树的加分subtree的右子树的加分subtree的根的分数若某个子树为空规定其加分为l叶子的加分就是叶结点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为(…n)且加分最高的二叉树tree。要求输出:()tree的最高加分()tree的前序遍历【输入格式】第行:一个整数n(n<)为节点个数。第行:n个用空格隔开的整数为每个节点的分数(分数<)。【输出格式】第行:一个整数为最高加分(结果不会超过)。第行:rl个用空格隔开的整数为该树的前序遍历。【输入样例】【输出样例】这道题目巧妙地将区间型动态规划和二叉树相结合既考查了二叉树的基本性质又考查了大家对动态规划的掌握不得不承认这是一道经典好题。同样这道题最后要求输出前序遍历只需要用递归建树即可这里就不多说了。具体的预处理过程和动态规划过程如下:预处理read(n)Fori:=tondoread(ai)Fori:=tondoForj:=tondoFi,j:=Fori:=ltondoFi,i:=aiDP过程Fori:=tondoForj:=ltonildoFork:=jtoijdoiffj,ij<fj,k*fk,ijakthenfj,ij:=fj,k*fkl,ijak其中Ak是读入的数组Fn同样为最终结果表示从第一个到第n个数进行建树的最大价值。小结:对于区间型动态规划的思想和具体的应用就是这些其实这类动态规划并不难关键在于领悟区间的含义更重要的是将这种思想进行变通灵活应用。另外在程序的实现过程中掌握一些技巧也是必需的这是轻松解题的关键最后希望大家能够通过此文轻松掌握区间型动态规划。第页共页

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/6

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利