动态规划-例题众多-详细讲解.ppt

动态规划参参与与竞竞赛赛的的同同学学应应由由竞竞争争关关系系和和独独立立关关系系（你你做做你你的的，我我干干我我的的，程程序序和和算算法法互互相相保保密密，彼彼此此津津津津乐乐道道于于对对方方的的失失败败和和自自己己的的成成功功）转转向向合合作作学学习习的的（通通过过研研讨讨算算法法、集集中中编编程程、互互测测数数据据等等互互相相合合作作的的方方式式完完成学习任务）成学习任务）1F(n)=1if n=0 or 1F(n-1)+F(n-2)if n 1l斐波纳契数列F(n)2递归递归vs动态规划动态规划递归版本:F(n)1if n=0 or n=1 then2return 13else4return F(n-1)+F(n-2)动态规划:F(n)1A0=A1 12for i 2 to n do3Ai Ai-1+Ai-24return An太慢太慢!有效率!算法复杂度是 O(n)3方法概要方法概要l构造一个公式，它表示一个问题的解是与它的子问题的解相关的公式.E.g.F(n)=F(n-1)+F(n-2).l为这些子问题做索引，以便它们能够在表中更好的存储与检索(i.e.,数组array【】)l以自底向上的方法来填写这表格;首先填写最小子问题的解.l这就保证了当我们解决一个特殊的子问题时,可以利用比它更小的所有可利用的子问题的解.由于历史原因,我们称这种方法为：动态规划动态规划.在上世纪40年代末(计算机普及很少时),这些规划设计是与”列表“方法相关的.4动态规划算法动态规划算法l算法思想 将待求解的问题分解成若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。l动态规划算法通常用于求解具有某种最优性质的问题。l动态规划算法的基本要素：最优子结构性质和重叠子问题。5l最优子结构性质：问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。l重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。对每个子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，不必重新求解。6动态规划动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长）问题；2.动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n1）的最优推导出n的最优7l动态规划算法的4个步骤：1.刻画最优解的结构特性.（一维，二维，三维数组）2.递归的定义最优解.（状态转移方程）3.以自底向上的方法来计算最优解.4.从计算得到的解来构造一个最优解.解决问题的基本步骤8大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点9例题一例题一.斐波纳契数列斐波纳契数列F F(n n)F(n)=1if n=0 or 1F(n-1)+F(n-2)if n 1步骤步骤1：用：用F（n）表示在斐波纳契数列中第）表示在斐波纳契数列中第n个数的值；个数的值；步骤步骤2：状态转移方程：状态转移方程：步骤步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解步骤步骤4：在数组中分析构造出问题的解；：在数组中分析构造出问题的解；10例题二例题二.输入输入n n，求出，求出n n！F(n)=1if n=0 or 1F(n-1)*nif n 1步骤步骤1：用：用F（n）表示）表示n！的值；！的值；步骤步骤2：状态转移方程：状态转移方程：步骤步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解11例题三：排队买票问题例题三：排队买票问题l一一场场演演唱唱会会即即将将举举行行。现现有有n个个歌歌迷迷排排队队买买票票，一一个个人人买买一一张张，而而售售票票处处规规定定，一一个个人人每每次次最最多多只只能能买买两两张张票票。假假设设第第i位位歌歌迷迷买买一一张张票票需需要要时时间间Ti（1in），队队伍伍中中相相邻邻的的两两位位歌歌迷迷（第第j个个人人和和第第j+1个个人人）也也可可以以由由其其中中一一个个人人买买两两张张票票，而而另另一一位位就就可可以以不不用用排排队队了了，则则这这两两位位歌歌迷迷买买两两张张票票的的时时间间变变为为Rj，假假如如Rjfi-1+Tithen7 fifi-1+Ti8returnf14例题四：求最长不降子序列例题四：求最长不降子序列1问题描述问题描述设有一个正整数的序列：设有一个正整数的序列：b1,b2,，bn，对于下标，对于下标i1i2im，若有，若有bi1bi2bim则称存在一个长度为则称存在一个长度为m的不下降序列。的不下降序列。例如，下列数列例如，下列数列13791638243718441921226315对于下标对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足，满足1316384463,则存则存在长度为在长度为5的不下降序列。的不下降序列。但是，我们看到还存在其他的不下降序列但是，我们看到还存在其他的不下降序列:i1=2，i2=3，i3=4，i4=8，i510，i6=11，i7=12，i8=13，满足：，满足：79161819212263，则存在长，则存在长度为度为8的不下降序列。的不下降序列。问题为：当问题为：当b1,b2,，bn给出之后，求出最长的不下降序列。给出之后，求出最长的不下降序列。步骤步骤1：用：用F（i）表示第）表示第i项到最后一项最长不下降序列的长度的值；项到最后一项最长不下降序列的长度的值；步骤步骤2：状态转移方程；：状态转移方程；di表示数列中第i项的值；步骤步骤3：以自底向上的：以自底向上的方法来计算最优解方法来计算最优解15拓展拓展1：拦截导弹拦截导弹（vijos1303）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）16拓展拓展2：低价购买：低价购买“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单：日期123456789101112价格686954646864706778629887最优秀的投资者可以购买最多4次股票，可行方案中的一种是：日期25610价格69686462输入输入第1行:N(1=N=5000)，股票发行天数第2行:N个数，是每天的股票价格。输出输出输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(=231)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。17拓展拓展3：合唱队形：合唱队形（vijis1098）N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK，则他们的身高满足T1.Ti+1TK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入的第一行是一个整数输入的第一行是一个整数N(2=N=100)，表示同学的总数。第一行有，表示同学的总数。第一行有n个整数，用空格分隔，第个整数，用空格分隔，第i个整数个整数Ti(130=Ti=230)是第是第i位同学的身高位同学的身高(厘厘米米)。输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。样例输入样例输入8186186150200160130197220样例输出：样例输出：418例题五例题五例题五例题五.马拦过河卒马拦过河卒马拦过河卒马拦过河卒问题描述问题描述:如图，如图，A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B点。卒行走规则：点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图控制点。例如上图C点上的马可以控制点上的马可以控制9个点（图中的个点（图中的P1，P2P8和和C）。卒不能通过对方马的控制点。）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n,m）(n,m为不超过20的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定:CA，同时CB）。现在要求你计算出卒从A点能够到达B点的路径的条数。输入输入:键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）不用盘错输出输出:屏幕输出一个整数（路径的条数）。输入输出样例输入输出样例:输入：6632输出：1719步骤步骤1：用：用F（X,Y）表示到棋盘上每个阶段）表示到棋盘上每个阶段(X,Y)的路径的路径条数；条数；步骤步骤2：状态转移方程：状态转移方程：步骤步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解分析：阶段：棋盘上的每个可走的点；每个阶段的求解；F（X,Y）=F(X-1,Y)+F(X,Y-1)其中，其中，F（0,0)=1F(0,Y)=1F(X,0)=120例题六：数字三角形问题例题六：数字三角形问题1问题描述设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走。如图10一1所示。问题：当三角形数塔给出之后，找出一条从第一层到达底层的路径，使路径的问题：当三角形数塔给出之后，找出一条从第一层到达底层的路径，使路径的值最大。若这样的路径存在多条，任意给出一条即可。值最大。若这样的路径存在多条，任意给出一条即可。21步骤步骤步骤步骤1 1二维数组二维数组D(X,y)描述问题，描述问题，D(X,y)表示从顶层到达第表示从顶层到达第X层第层第y个位置的最小路径得分。个位置的最小路径得分。步骤步骤步骤步骤2 2：状态转移方程：状态转移方程：状态转移方程：状态转移方程阶段分析：D(1,1)=13到第x层的第y个位置有两种可能，要么走右分支得到，要么走左分支得到。l D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y)l D(1,1)a(1,1)22拓展：栈（拓展：栈（vijos1122）【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）23使用这两种操作，由一个操作数序列就可以得到一系列的输出使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由序列，下图所示为由1 2 3生成序列生成序列2 3 1的过程。（原始状态如的过程。（原始状态如上图所示）上图所示）12312313222323124你的程序将对给定的你的程序将对给定的n，计算并输出由操作数序列，计算并输出由操作数序列1，2，n经过操作经过操作可能得到的输出序列的总数。可能得到的输出序列的总数。【输入格式输入格式】输入文件只含一个整数输入文件只含一个整数n（1n18）【输出格式输出格式】输出文件只有一行，即可能输出序列的总数目输出文件只有一行，即可能输出序列的总数目【输入样例输入样例】3【输出样例输出样例】525例题七：最长公共子序列例题七：最长公共子序列l一个给定序列的子序列是在该序列中删去若干元素后得到的序列。l给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。l最长公共子序列:公共子序列中长度最长的子序列。l最长公共子序列问题给定两个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的一个最长公共子序列。l例如:X=(A,B,C,B,D,A,B)X的子序列:l所有X的子集(集合中元素按原来在X中的顺序排列)(A,B,D),(B,C,D,B),等等.26例子例子X=(A,B,C,B,D,A,B)X=(A,B,C,B,D,A,B)Y=(B,D,C,A,B,A)Y=(B,D,C,A,B,A)l(B,C,B,A)和(B,D,A,B)都是X和Y的最长公共子序列(长度为4)l但是,(B,C,A)就不是X和Y的最长公共子序列27穷举法穷举法l对于每一个Xm的子序列,验证它是否是Yn的子序列.lXm有2m个子序列l每个子序列需要o(n)的时间来验证它是否是Yn的子序列.l从Yn的第一个字母开始扫描下去,如果不是则从第二个开始l运行时间:o(n2m)28l给定一个序列Xm=(x1,x2,xm),我们定义Xm的第i个前缀为:Xi=(x1,x2,xi )i=0,1,2,mci,j为序列Xi=(x1,x2,xi)和Yj=(y1,y2,yj)的最长公共子序列的长度.分析分析分析分析:最优子结构性质最优子结构性质最优子结构性质最优子结构性质：设序列Xm=x1,x2,xm和Yn=y1,y2,yn的一个最长公共子序列为Zk=z1,z2,zk，则1.若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。2.若xmyn，且zkxm，则Zk是Xm-1和Yn的最长公共子序列。3.若xmyn，且zkyn，则Zk是Xm和Yn-1的最长公共子序列。步骤步骤1步骤步骤229状态转移方程状态转移方程yj:xmy1y2ynx1x2xii012nm120firstsecond步骤步骤330附加信息附加信息yj:DACFABxiji012nm120矩阵bi,j:l它告诉我们要获得最优结果应该如何选择l如果xi=yjbi,j=1l如果ci-1,jci,j-1bi,j=2否则bi,j=333CDci,j-1ci-1,j31LCS-LENGTH(X,Y,m,n)1fori1tomdoci,002forj0tondoc0,j03fori1tomdo4forj 1tondo5ifxi=yj6thenci,jci-1,j-1+17bi,j“”8elseifci-1,jci,j-19thenci,jci-1,j10bi,j“”11elseci,jci,j-112bi,j“”13returncandb运行时间:(nm)32例子例子X=(B,D,C,A,B,A)Y=(A,B,C,B,D,A,B)0126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222 1122 331 222331232 3 4 1223 44如果xi=yjbi,j=“”如果 ci-1,jci,j-1bi,j=“”否则bi,j=“”33找出最长共同子序列找出最长共同子序列PRINT-LCS(b,X,i,j)1ifi=0orj=02thenreturn3ifbi,j=4thenPRINT-LCS(b,X,i-1,j-1)5printxi6elseifbi,j=7thenPRINT-LCS(b,X,i-1,j)8elsePRINT-LCS(b,X,i,j-1)34例题例题8：0-1背包问题背包问题l小偷有一个可承受W的背包l有n件物品:第i个物品价值vi且重wil目标:l找到xi使得对于所有的xi=0,1,i=1,2,.,nwixiW并且 xivi最大部分背包问题35最优子结构最优子结构l考虑最多重W的物品且价值最高l如果我们把j物品从背包中拿出来剩下的装载一定是取自n-1个物品使得不超过载重量W wj并且所装物品价值最高的装载360-1背包问题的动态规划背包问题的动态规划对于每一个物品对于每一个物品i，都有两种情况需要考虑，都有两种情况需要考虑第第1种情况种情况:物品物品i的重量的重量wiw,即小偷不拿物品即小偷不拿物品iP(i,w)=P(i-1,w)步骤步骤步骤步骤1 1P(i,w)考虑前考虑前i件物品所能获得的最高价值件物品所能获得的最高价值,其中其中w是是背包的承受力背包的承受力步骤步骤步骤步骤2 2阶段分析：阶段分析：阶段分析：阶段分析：P（i，w）P(i-1,w)当wiwthen6Pi,wPi-1,w;7else8Pi,wmaxPi-1,w,Pi-1,w-wi+vi运行时间:(nW)380-1背包问题的动态规划背包问题的动态规划0:n1w-wiWi-10firstP(i,w)=maxvi+P(i-1,w-wi),P(i-1,w)带走物品i不带走物品iiwsecond39P(i,w)=maxvi+P(i-1,w-wi),P(i-1,w)0123451234W=5012121212101222222210122230321015253037P(1,1)=P(1,2)=P(1,3)=P(1,4)=P(1,5)=P(2,1)=P(2,2)=P(2,3)=P(2,4)=P(2,5)=P(3,1)=P(3,2)=P(3,3)=P(3,4)=P(4,5)=P(4,1)=P(4,2)=P(4,3)=P(4,4)=P(4,5)=max12+0,0=12max12+0,0=12max12+0,0=12max12+0,0=12max10+0,0=10max10+0,12=12max10+12,12=22max10+12,12=22max10+12,12=22P(2,1)=10P(2,2)=12max20+0,22=22max20+10,22=30max20+12,22=32P(3,1)=10max15+0,12=15max15+10,22=25max15+12,30=30max15+22,32=370P(0,1)=0wi40构造最优解法构造最优解法01234512340121212121012222222101222303210152530370l从P(n,W)开始l当往左上走物品i被带走l当直往上走物品i未被带走物品4物品2物品141子问题的重复子问题的重复0:n1Wi-10P(i,w)=maxvi+P(i-1,w-wi),P(i-1,w)iw例如:所有用灰色表示的子问题都取决于P(i-1,w)42子问题的重复子问题的重复100101108108681006282861001623823816510000000000000111111111例子:n=5,p=6,3,5,4,6,w=2,2,6,5,4,W=1043拓展拓展1：装箱问题：装箱问题（vijos1133）有一个箱子容量为v(正整数，ov20000)，同时有n个物品(on30)，每个物品有一个体积(正整数)。要求从n个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。输入格式输入格式InputFormat第一行，一个整数，表示箱子容量；第二行，一个整数，表示有n个物品；接下来n行，分别表示这n个物品的各自体积。输出格式输出格式OutputFormat一个整数，表示箱子剩余空间。样例输入样例输入SampleInput2468312797样例输出样例输出SampleOutput044拓展拓展2：采药：采药(vijos1104)辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？如果你是辰辰，你能完成这个任务吗？输入格式输入格式InputFormat输入的第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出格式输出格式OutputFormat输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。样例输入样例输入SampleInput7037110069112样例输出样例输出SampleOutput345拓展拓展3：开心的金明：开心的金明（vijos1317）金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1.jk，则所求的总和为：vj1*wj1+.+vjk*wjk请你帮助金明设计一个满足要求的购物单.输入格式输入格式InputFormat输入的第1行，为两个正整数，用一个空格隔开：Nm（其中N（30000）表示总钱数，m(25)为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格（v10000），p表示该物品的重要度（15）46输出格式输出格式OutputFormat输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）样例输入样例输入SampleInput1000580024005300540032002样例输出样例输出SampleOutput390047拓展拓展4：金明的预算方案：金明的预算方案(vijos1313)金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。48输入格式输入格式InputFormat输入文件的第1行，为两个正整数，用一个空格隔开：Nm其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v0，表示该物品为附件，q是所属主件的编号）输出格式输出格式OutputFormat输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。样例输入样例输入SampleInput100058002040051300514003050020样例输出样例输出SampleOutput220049例题例题9：石子归并：石子归并描述：在一个圆形操场的四周摆放着描述：在一个圆形操场的四周摆放着N堆石子堆石子(N=100),现要将石子有次序现要将石子有次序地合并成一堆地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆并将新的一堆的石子数的石子数,记为该次合并的得分记为该次合并的得分.编一程序编一程序,由文件读入堆栈数由文件读入堆栈数N及每堆栈的石及每堆栈的石子数子数(=20).(!)选择一种合并石子的方案选择一种合并石子的方案,使用权得做使用权得做N1次合并次合并,得分的总和最小得分的总和最小;(2)选择一种合并石子的方案选择一种合并石子的方案,使用权得做使用权得做N1次合并次合并,得分的总和最小得分的总和最小;输入数据输入数据:第一行为石子堆数第一行为石子堆数N;第二行为每堆的石子数第二行为每堆的石子数,每两个数之间用一个空格每两个数之间用一个空格分隔分隔.输出数据输出数据:从第一至第从第一至第N行为得分最小的合并方案行为得分最小的合并方案.第第N+1行是行是空行空行.从第从第N+2行到第行到第2N+1行是得分最大合并方案行是得分最大合并方案.每种合并方案用每种合并方案用N行表示行表示,其中第其中第i行行(1=i=N)表示表示第第i次合并前各堆的石子数次合并前各堆的石子数(依顺时针次序输出依顺时针次序输出,哪哪一堆先输出均可一堆先输出均可).要求将待合并的两堆石子数以相要求将待合并的两堆石子数以相应的负数表示应的负数表示.输入输出范例输入输出范例:输入输入:44594输出输出:最小最小43最大最大5450输入输入:44594输出输出:拓：输出合并的方案：拓：输出合并的方案：51用用i，j表示一个从第表示一个从第i堆数起，顺时针数堆数起，顺时针数j堆时的子序列堆时的子序列第第i堆、第堆、第i堆、堆、第（、第（ij1）modn堆堆步骤步骤步骤步骤1 1fi，j将子序列将子序列i，j中的中的j堆石子合并成一堆堆石子合并成一堆的最佳得分和；（结果数组）的最佳得分和；（结果数组）ci，j将将i，j一分为二，其中子序列的堆一分为二，其中子序列的堆数；（记录分隔点）数；（记录分隔点）打印合并方案时使用打印合并方案时使用52显然，对每一堆石子来说，它的fi，ci，（iN）对于子序列i，j来说，若求最小得分总和，fi，j的初始值为；若求最大得分总和，fi，j的初始值为。（iN，jN）。规划的方向是顺推。先考虑含二堆石子的N个子序列（各子序列分别从第堆、第堆、第N堆数起，顺时针数堆）的合并方案f，f，fN，c，c，cN，然后考虑含三堆石子的个子序列（各子序列分别从第堆、第堆、第堆数起，顺时针数堆）的合并方案f，f，fN，c，c，cN，依次类推，直至考虑了含N堆石子的N个子序列（各子序列分别从第堆、第堆、第N堆数起，顺时针数N堆）的合并方案f，N，f，N，fN，Nc，N，c，N，cN，N最后，在子序列，N，N，N，N中，选择得分总和（f值）最小（或最大）的一个子序列i，N（iN），由此出发倒推合并过程。阶段分析：阶段分析：阶段分析：阶段分析：53例如对（图624）中的堆石子，按动态规划方程顺推最小得分和。依次得出含二堆石子的个子序列的合并方案f，f，f，c，c，c，f，f，f，c，c，c，含三堆石子的个子序列的合并方案f，f，f，c，c，c，f，f，f，c，c，c，含四堆石子的个子序列的合并方案f，f，f，c，c，c，f，f，f，c，c，c，例题：例题：54步骤步骤步骤步骤2 2：状态转移方程：状态转移方程：状态转移方程：状态转移方程F(I,j)=f(i,1)=0j=1,1=i=nmaxfi，kfx，j-kt,1=k=j-1其中，x（ik1）modn+1即第i堆起，顺时针数k1堆的堆序号。tai+ai+1+.+aj,即将分开的两堆合并为一堆的得分。ci，jkfi，jfi，kfx，j-kt（，）55附加信息：打印合并方案附加信息：打印合并方案附加信息：打印合并方案附加信息：打印合并方案56拓展拓展1：能量项链能量项链（vijos1312）在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。57输入格式输入格式InputFormat输入文件的第一行是一个正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当1iN时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出格式输出格式OutputFormat输出文件只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。样例输入样例输入SampleInput423510样例输出样例输出SampleOutput71058拓展拓展2：数字游戏数字游戏（vijos1218）【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共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取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。24-1359