历届NOIp动态规划梳理课件.pptVIP

历届NOIp动态规划梳理,动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，以得到全局最优策略。动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来，动态规划几乎每次都出现在NOIp的赛场上，而且还有越来越多的趋势。因此，掌握基本的NOIp动态规划题是至关重要的。,动态规划实质：,枚举,+,递推,状态,状态转移方程,SampleProblem1,1,3,5,9,1,从树的根到树的叶节点，最多能取多少数？,贪心：答案错误,暴力搜索：如果数据大会超时,动态规划！,我们先将NOIp里的动态规划分分类：,最长不降子序列背包方格取数石子归并状态压缩数学递推顺序递推,最长不降子序列,设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)且a(i)a(j)(i，j=n)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3ie且有a(i1)a(i2)a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。最长的不下降序列就是求长度最长的子序列。Fori:=1TonDoForj:=1Toi-1DoIf(aiTK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=TifjThenfj:=fj-ai+bi;Ff:=fj-ai+bi;01Ifj+si,1,1fj+si,1,1Thenfj+si,1,1:=Ff+si,1,2;10Ifj+si,2,1fj+si,2,1Thenfj+si,2,1:=Ff+si,2,2;11Ifj+si,1,1+si,2,1fj+si,1,1+si,2,1Thenfj+si,1,1+si,2,1:=Ff+si,1,2+si,2,2;End;End;,背包,SampleProblem5,邮票面值设计（NOIp1999）给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1MAX之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为1分、4分，则在1分6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。【样例】INPUTN=3K=2OUTPUT13MAX=7,背包,如果你一看到这道题目就想到搜索，那么,恭喜你，你答对了！,方格取数,SampleProblem6,方格取数（NOIp2000）设有N*N的方格图(N=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。,方格取数,13+14+4+21+15=67,方格取数,一取方格数：fi,j:=maxfi-1,j,fi,j-1;现在要做的数二取方格数，是否还能像一取方格数那样如法炮制呢？,答案是肯定的！,我们观察一下它的路径。fi,j是从fi-1,j或者fi,j-1走来。无论是从fi-1,j还是fi,j-1走来，要么是x坐标+1，要么是y坐标+1，总归x坐标的值+y坐标的值一定比前一个多1。我们来验证一下：,方格取数,X坐标（3，3）3+3=6Y坐标（3，4）3+4=7Z坐标（4，4）4+4=8,方格取数,再观察，我们发现，走第n步时，能走到点是固定的。观察其坐标我们发现，第n步能走到的点其坐标和为n-1。,因此，走到第n步时，x坐标和y坐标的和就知道=n+1，这样我们就不必同时知道2条路线x坐标和y坐标了，知道其中一个t，另外一个就可以用n+1-t来表示了。,于是此题迎刃而解！,方格取数,用fx,i,j表示走到第x步时，第1条路线走到横坐标为i的地方，第2条路线走到了横坐标为j的地方。这样，我们只要枚举x，i，j，就能递推出来了。,Forx:=3Tom+nDoFori:=1ToMin(x,n)DoForj:=1ToMin(x,n)DoBeginfx,i,j:=Max(fx-1,i,j,fx-1,i-1,j,fx-1,i,j-1,fx-1,i-1,j-1);Ifi=jThenInc(fx,i,j,ai,x-i)ElseBeginInc(fx,i,j,ax-i,i);Inc(fx,i,j,ax-j,j);End;End;,同样三取方格数只要fx,i,j,k用同样的方法即可。,方格取数,传纸条（NOIp2008）【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。,SampleProblem7,石子归并,SampleProblem8,石子归并原题【题目描述】在一个圆形操场的四周摆放着N堆石子(N=100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(=20).选择一种合并石子的方案,使用权得做N1次合并,得分的总和最小。【输入数据】第一行为石子堆数N;第二行为每堆的石子数,每两个数之间用一个空格分隔。【输出数据】一行，最小总和。【输入】44594【输出】22,2019/12/15,29,可编辑,石子归并,4,5,9,4,石子归并,我们用fi,j表示以i堆石子为开头，以j堆石子为结尾的一系列石子归并起来的最小总和。因为题目中说，只能归并相邻的两堆石子。所以，fi,j这一系列石子必然由fi,k和fk+1,j（i=kfj,k+fk+1,j+iThenfj,j+i:=fj,k+fk+1,j+i;fj,j+i:=fj,j+i+Sumj,j+i;End;这样，求归并的最大值也是同样的方法，不再赘述。,石子归并,SampleProblem9,能量项链（NOIp2006）在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。,石子归并,SampleProblem10,乘积最大（NOIp2000）【问题描述】设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。【输入】程序的输入共有两行：第一行共有2个自然数N，K（6N40，1K6）第二行是一个长度为N的数字串。【输出】输出所求得的最大乘积（一个自然数）。【样例输入】421231【样例输出】62,石子归并,这道题目要求把一个长度为n的数字串分成k段，使得每段的乘积最大。通过刚才的石子归并思想，我们可以用fi,j表示前i个数字我分了j段所能得到的最大值，那么fi,j就可以从fk,j-1（前k个数字分成了j-1段）推来，因为fi,j就是fk,j-1和（k+1i）这段数字串的乘积。于是状态转移方程即可得出：fi,j:=Maxfk,j-1*Numberk+1,i(j-1=ki)其中Numberk+1,j表示数字串从第k+1位到第i位转换成数字的值。对于题目中所说的具有很强枚举意味的变量（如k段，n次等），一般将其放入状态中枚举。而诸如最大值最小值之类的变量，一般放入数组中作为值递推。,SampleProblem11,统计单词个数（NOIp2001）【问题描述】给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1k=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。【样例输入】3thisisabookyouareaoh4isaoksab【样例输出】7this/isabookyoua/reaoh,石子归并,石子归并,看到这道题目应该马上有这种意识了：和乘积最大神似！所以本题除了求出ij之间有多少单词以外基本上就没什么难度了。预处理出ij之间有多少单词，其实也可以用DP。首先，题目告诉我们，如果a是b的前缀，那么b肯定没用了（为什么）。所以第一步删串。之后的任务就是求单词数了。令si,j表示ij之间有多少个单词，那么si,j=si,j-1+以第j位为结尾，包含在ij这段串里的单词个数。如串cabce，单词有cab、abc。明显第13之间有1个单词，而14之间呢？13有的它肯定也有，再去枚举单词中有没有是cabc后缀的单词。最终f1,4=f1,3+1。,SampleProblem12,矩阵取数游戏（NOIp2007）【问题描述】帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分=被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4.游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写个程序，对于任意矩阵，可以求出取数后的最大得分。【输入】第一行为两个用空格隔开的整数n和m。第2n+1行为n*m矩阵，其中每行有m个用单个空格隔开【输出】一个整数，即输入矩阵取数后的最大的分。【限制】60%的数据满足：1=n,m=30，答案不超过106100%的数据满足：1=n,m=80，0=aij=1000,石子归并,改变一下题目的叙述：每行有m个数，倒数第i次取的得分是ai*2(m+1-i)；倒推，因为每次只能取一段中的头或尾，所以剩下的永远是连续的一段，每次加入头或尾。把一段的头和尾看做一堆石子，把ai*2(m+1-i)看做每次归并的加分，每次归并不是取相邻的，而是取一段中的头或尾就是石子归并。用fi,j,k表示第i行，取了一些数后剩下连续的一段从j到k，那么状态转移方程就很好写了：fi,j,k:=Maxfi,j-1,k+aj-1*2(m-k+j-1)fi,j,k+1+ak+1*2(m-k+j-1);这道题目还要高精度，建议写好非高精的DP再修改成高精度的。,石子归并,状态压缩,过河（NOIp2005）【问题描述】在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。【输入文件】第一行一个正整数L（1=L=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1=S=T=10，1fi-jThenfi:=fi-j;但是有个地方我们忽略了，那就是数据规模。L最大有109，第一个For就已经无法承受庞大的时间限制和空间限制了。所以，这种方法需要进行改进。而改进的方法，就是状态压缩。,状态压缩,我们可以发现题目的一个玄机：虽然L很大，但是M却很小，也就是说：,石子很稀疏,石子稀疏对我们解题有什么帮助呢？我们来看一下下面的推断：,第一种情况：当s=t时，很简单，青蛙踩到的石头肯定是s的倍数，那么只要统计一下所有石子中有多少是s的倍数，输出即可。,第二种情况：st我们先来看一组数据。s=4，t=5。,从数据中我们看到，12以后的点全部都是可以到达的了。如果s=4，t=5，在一段100000的距离中没有石头，其实12以后的点都是不用递推就知道肯定能到达的。那么我们用原始的方法做就会浪费很大的资源。所以当s=4，t=5时，如果一段没有石头的区间长度在4*5=20以外，那么我们只要递推前20就可以了，因为20后面的情况是一样的（仔细想想为什么？）。,状态压缩,假设s=3，t=5，那么11=3+4+4就也可以到达了。所以，只有当t=s+1时，连续的点的起始位置才能尽量后面。最坏情况就是s=9，t=10了（仔细想想为什么？）。跟前面的s=4，t=5的情况一样，其实s=9，t=10时只要一段没有石头的区间长度在90之外，我们都把它当做90对待就可以了。因此，我们每次对于一段没有石头的区间长度为x，如果xt(t-1)时，我们就把它当做t(t-1)处理。这样，最大的复杂度就是t(t-1)*（石头个数+1）=90*101=9090，比之前的复杂度大大降低。这种方法叫状态压缩，我们这题用的方法叫离散化。至此，过河完美AC！,状态压缩,SampleProblem14,数的划分（NO