历届NOIp动态规划梳理...ppt

《历届NOIp动态规划梳理...ppt》由会员分享，可在线阅读，更多相关《历届NOIp动态规划梳理...ppt（54页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，以得到全局最优策略。动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来，动态规划几乎每次都出现在NOIp的赛场上，而且还有越来越多的趋势。因此，掌握基本的NOIp动态规划题是至关重要的。动态规划实质：枚举+递推状态状态状态转移方程状态转移方程Sample Problem1Sample Problem113591 从树的根到树的叶节点，最多能取多少数？贪心贪心：答案错误答案错误暴

2、力搜索暴力搜索：如果数据大会超时如果数据大会超时 我们先将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。若存在i1i2i3 ie 且有a(i1)a(i2)a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。最长的不下降序列就是求长度

3、最长的子序列。For i:=1 To n DoFor j:=1 To i-1 DoIf(ai=aj)And(fifj+1)Then fi:=fj+1;合唱队形（合唱队形（NOIp2004）【问题描述】【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他 们 的 身 高 分 别 为 T1，T2，TK，则 他 们 的 身 高 满 足T1.Ti+1TK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】【输入文件

4、】输入文件第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高。【输出文件】【输出文件】输出文件包括一行，这一行只包含一个整数，就是最少需要几位同学出列。Sample Problem2Sample Problem2拦拦截截导弹导弹（NOIp1999NOIp1999）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可

5、能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）Sample Problem3Sample Problem3反例：9 8 7 1 10 6 5 49 8 7 1 10 6 5 49 8 7 1 10 6 5 4 1 10 1 10 10 109 8 7 1 10 6 5 49 8 7 1 10 6 5 4 10

6、6 5 4 10 6 5 401背包：有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使价值总和最大。完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。For i:=1 To n DoFor j:=Max Downto ai Do(ai To Max)If fjfj-ai+bi Then fj:=fj-ai+bi;Sample Problem4Sample Problem4金明的预算方案（金明的预算方案（NOIp2006）【

7、问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N

8、元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。Sample Problem4Sample Problem4【输入文件】第1行，为两个正整数N m（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q（其中v表示该物品的价格（v0，表示该物品为附件，q是所属主件的编号

9、）【输出文件】只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。【输入样例】1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【输出样例】2200 For i:=1 To n Do For j:=m Downto ai Do If fj-ai-1 then Begin00 If fj-ai+bifj Then fj:=fj-ai+bi;Ff:=fj-ai+bi;01 If j+si,1,1fj+si,1,1 Then fj+si,1,1:=Ff+si,1,2;10 If j+si,2,1fj+si,2,1 Then fj+si,2,1:=Ff

10、+si,2,2;11 If j+si,1,1+si,2,1fj+si,1,1+si,2,1 Then fj+si,1,1+si,2,1:=Ff+si,1,2+si,2,2;End;End;Sample Problem5Sample Problem5邮票面值设计（邮票面值设计（NOIp1999）给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1MAX之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为1分、4分，则在1分6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；

11、如果面值分别为1分、3分，则在1分7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。【样例】INPUTN=3 K=2 OUTPUT1 3 MAX=7 如果你一看到这道题目就想到搜索，那么 这道题目就是搜索。那么为什么它出现在动态规划的专题中的？是因为 你DFS生成一组邮票面值之后，你需要用某种方法把它能达到的面额都枚举出来。而这个工作如果要让枚Cnm举来做，那么太浪费资源了。枚举的复杂度是 ，尽管n、m很小，但是在大DFS的前提下就不怎么划算了。因此我们使用DP来枚举出所有可能的面额，而方法，就是传说中的完全背

12、包（经过处理的）。Sample Problem6Sample Problem6方格取数方格取数（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;现在要做的数二取方格数，是否还能像一取方格数那样如法炮制呢？答案是肯定的

13、！我们观察一下它的路径。fi,j是从fi-1,j或者fi,j-1走来。无论是从fi-1,j还是fi,j-1走来，要么是x坐标+1，要么是y坐标+1，总归x坐标的值+y坐标的值一定比前一个多1。我们来验证一下：XY ZX坐标（3，3）3+3=6Y坐标（3，4）3+4=7Z坐标（4，4）4+4=8X、Y、Z的坐标和在不断增加，每次+1。再观察，我们发现，走第n步时，能走到点是固定的。观察其坐标我们发现，第n步能走到的点其坐标和为n-1。因此，走到第n步时，x坐标和y坐标的和就知道=n+1，这样我们就不必同时知道2条路线x坐标和y坐标了，知道其中一个t，另外一个就可以用n+1-t来表示了。用fx,i

14、,j表示走到第x步时，第1条路线走到横坐标为i的地方，第2条路线走到了横坐标为j的地方。这样，我们只要枚举x，i，j，就能递推出来了。For x:=3 To m+n Do For i:=1 To Min(x,n)Do For j:=1 To Min(x,n)Do Begin fx,i,j:=Max(fx-1,i,j,fx-1,i-1,j,fx-1,i,j-1,fx-1,i-1,j-1);If i=j Then Inc(fx,i,j,ai,x-i)Else Begin Inc(fx,i,j,ax-i,i);Inc(fx,i,j,ax-j,j);End;End;同样三取方格数只要fx,i,j,k用

15、同样的方法即可。传纸条（传纸条（NOIp2008）【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说

16、如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。Sample Problem7Sample Problem7Sample Problem8Sample Problem8石子归并原题石子归并原题【题目描述】在一个圆形操场的四周摆放着N堆

17、石子(N=100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(=20).选择一种合并石子的方案,使用权得做N1次合并,得分的总和最小。【输入数据】第一行为石子堆数N;第二行为每堆的石子数,每两个数之间用一个空格分隔。【输出数据】一行，最小总和。【输入】44 5 9 4【输出】22 4594598总和：8913总和：2122总和：43 我们用fi,j表示以i堆石子为开头，以j堆石子为结尾的一系列石子归并起来的最小总和。因为题目中说，只能归并相邻的两堆石子。所以，fi,j这一系列石

18、子必然由fi,k和fk+1,j（i=kj）这两堆石子归并而来。只要在所有的fi,k+fk+1,j中取个最小值（就是原来此次没归并前的最小值），加上自己本身所有石子的和（因为归并一次的代价是所有石子的总和），就是我们要求的fi,j。因此，状态转移方程为：jn=ian;(i=kfj,k+fk+1,j+i Then fj,j+i:=fj,k+fk+1,j+i;fj,j+i:=fj,j+i+Sumj,j+i;End;这样，求归并的最大值也是同样的方法，不再赘述。Sample Problem9Sample Problem9能量项链（能量项链（NOIp2006）在Mars星球上，每个Mars人都随身佩带着

19、一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计

20、一个聚合顺序，使一串项链释放出的总能量最大。例如：设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。Sample Problem10Sample Problem10乘积最大（乘积最大（NOIp2000）【问题描述】设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分

21、法，使得这K+1个部分的乘积能够为最大。【输入】程序的输入共有两行：第一行共有2个自然数N，K（6N40，1K6）第二行是一个长度为N的数字串。【输出】输出所求得的最大乘积（一个自然数）。【样例输入】4 21231【样例输出】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=k

22、i)其中Numberk+1,j表示数字串从第k+1位到第i位转换成数字的值。对于题目中所说的具有很强枚举意味的变量（如k段，n次等），一般将其放入状态中枚举。而诸如最大值最小值之类的变量，一般放入数组中作为值递推。Sample Problem11Sample Problem11统计单词个数（统计单词个数（NOIp2001）【问题描述】给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1k=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再

23、用。例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。【样例输入】3thisisabookyouareaoh4isaoksab【样例输出】7 this /isabookyoua /reaoh 看到这道题目应该马上有这种意识了：和乘积最大神似！所以本题除了求出ij之间有多少单词以外基本上就没什么难度了。预处理出ij之间有多少单词，其实也可以用DP。首先，题目告诉我们，如果a是b的前缀，那么b肯定没用了（为什么）。所以第一步删串。之后的任务就是求单词数了。令si,j表示ij之间有多少个单词，那么si,j=si,j

24、-1+以第j位为结尾，包含在ij这段串里的单词个数。如串cabce，单词有cab、abc。明显第13之间有1个单词，而14之间呢？13有的它肯定也有，再去枚举单词中有没有是cabc后缀的单词。最终f1,4=f1,3+1。Sample Problem12Sample Problem12矩阵取数游戏（矩阵取数游戏（NOIp2007）【问题描述】帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得

25、分值，为每行取数的得分之和；每行取数的得分=被取走的元素值*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)；倒推，因为每次只能取一段中的头或尾，所以剩下的永远

26、是连续的一段，每次加入头或尾。把一段的头和尾看做一堆石子，把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）【问题描述】在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过

27、的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。【输入文件】第一行一个正整数L（1=L=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1=S=T

28、=10，1=M fi-j+1 Then fi:=fi-j+1 Else If fifi-j Then fi:=fi-j;但是有个地方我们忽略了，那就是数据规模。L最大有109，第一个For就已经无法承受庞大的时间限制和空间限制了。所以，这种方法需要进行改进。而改进的方法，就是状态压缩。我们可以发现题目的一个玄机：虽然L很大，但是M却很小，也就是说：石子稀疏对我们解题有什么帮助呢？我们来看一下下面的推断：第一种情况：当s=t时，很简单，青蛙踩到的石头肯定是s的倍数，那么只要统计一下所有石子中有多少是s的倍数，输出即可。第二种情况：st 我们先来看一组数据。s=4，t=5。从数据中我们看到，12以

29、后的点全部都是可以到达的了。如果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之外，我们都把它当做9

30、0对待就可以了。因此，我们每次对于一段没有石头的区间长度为x，如果xt(t-1)时，我们就把它当做t(t-1)处理。这样，最大的复杂度就是t(t-1)*（石头个数+1）=90*101=9090，比之前的复杂度大大降低。这种方法叫状态压缩，我们这题用的方法叫离散化。至此，过河完美AC！Sample Problem14Sample Problem14数的划分（数的划分（NOIp2001NOIp2001）【问题描述问题描述】将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法。【输

31、入】n，k(6n=200，2=k=j Then For t:=1 To j Do fi,j:=fi,j+fi-j,t;时间复杂度是你n*k2的。虽然可以轻松过这题，但如果n=50000，k=j Then fi,j:=fi-1,j-1+fi-j,j;最后加点预处理，此题完美就AC了！反思：解决此类题目，必先学好数学！Sample Problem15Sample Problem15加分二叉树（加分二叉树（NOIp2003）【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree

32、及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分 subtree的右子树的加分subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分 （2）tree的前序遍历【输入格式】第1行：一个整数n（n30），为节点个数。第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。因为此题给我们的是中序遍历，所以如果ai为根，那么a1ai-1就是这棵树的左子树，ai+1an就

33、是这棵树的右子树。同样的如果j是a1ai-1这棵子树的根，那么a1aj-1就是左子树中的左子树，aj+1ai-1就是左子树中的右子树，依次类推。这样，我们只要枚举ij这个区间和枚举这个区间的根k就可以了。至于路径，记录一下就可以了。For i:=1 To n-1 DoFor j:=1 To n-i DoFor k:=j To j+i DoIf fj,k-1*fk+1,j+i+akfj,j+i Then fj,j+i:=fj,k-1*fk+1,j+i+ak;总结：动态规划是NOIp中的一类大问题，它在联赛中考的几率是99%。动态规划的核心就是“状态”和“状态转移方程”，有了这两样东西，或许还要再

34、加点DFS、贪心、状态压缩、单调队列等来优化动态规划，基本上就可以放心DP了。1.在处理问题的过程中，要考虑全面、思索深入、抓准题目中的信息，适当进行筛选，作出合理的决策；3.平时多积累，要熟悉各种动态规划类型及其变种，如Floyd等；还要全面了解其他算法来辅助；2.认清动态规划本质，别把最长不降子序列当成背包来做，把石子归并当成数学问题来做；附录：相关练习题目最长不降子序列最长不降子序列：p1061背包背包：p1025 p1057 p1104 p1133 p1198 p1222 p1334方格取数方格取数：p1143 p1280 p1364 p1121石子归并石子归并：p1218 p1455 数学递推数学递推：p1073 p1136 p1210顺序递推顺序递推：p1006 p1011 p1014 p1063 p1139 p1232 p1235 p1292 p1623 树形动态规划树形动态规划：p1144 p1180限定数目限定数目：p1037 p1331 p1386数据结构优化数据结构优化：p1404 p1617其他其他：p1335 p1431 p1485