《历届NOIp动态规划梳理..优秀PPT.ppt》由会员分享，可在线阅读，更多相关《历届NOIp动态规划梳理..优秀PPT.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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=
4、i=K)。你你的的任任务务是是，已已知知全全部部N位位同同学学的的身身高高，计计算算最最少少须须要要几位同学出列，可以使得剩下的同学排成合唱队形。几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】【输入文件】输输入入文文件件第第一一行行是是一一个个整整数数N(2=N=100)，表表示示同同学学的的总总数数。第第一一行行有有n个个整整数数，用用空空格格分分隔隔，第第i个个整整数数Ti(130=Ti=230)是第是第i位同学的身高。位同学的身高。【输出文件】【输出文件】输输出出文文件件包包括括一一行行，这这一一行行只只包包含含一一个个整整数数，就就是是最最少须要几位同学出列。少须要几位同学
5、出列。Sample Problem2Sample Problem2拦拦截截导弹导弹（NOIp1999NOIp1999）某某国国为为了了防防卫卫敌敌国国的的导导弹弹攻攻击击，发发展展出出一一种种导导弹弹拦拦截截系系统统。但但是是这这种种导导弹弹拦拦截截系系统统有有一一个个缺缺陷陷：虽虽然然它它的的第第一一发发炮炮弹弹能能够够到到达达随随意意的的高高度度，但但是是以以后后每每一一发发炮炮弹弹都都不不能能高高于于前前一一发发的的高高度度。某某天天，雷雷达达捕捕获获到到敌敌国国的的导导弹弹来来袭袭。由由于于该该系系统统还还在在试试用用阶阶段段，所所以以只只有有一一套套系系统统，因因此此有有可可能能不不
6、能能拦拦截截全部的全部的导弹导弹。输输入入导导弹弹依依次次飞飞来来的的高高度度（雷雷达达给给出出的的高高度度数数据据是是不不大大于于3000030000的的正正整整数数），计计算算这这套套系系统统最最多多能能拦拦截截多多少少导导弹弹，假假如要如要拦拦截全部截全部导弹导弹最少要配最少要配备备多少套多少套这这种种导弹拦导弹拦截系截系统统。样样例：例：INPUT OUTPUT INPUT OUTPUT 389 389 207 207 155 155 300 300 299 299 170 170 158 158 65 65 6 6（最最多多能能拦拦截截的的导弹导弹数）数）2 2（要要拦拦截截全全部部
7、导导弹弹最少要配最少要配备备的系的系统统数）数）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 5 4 10 6 5 401背包：有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使价值总和最大。完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费
8、用总和不超过背包涵量，且价值总和最大。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）【问题描述】【问题描述】金明今日很快乐，家里购置的新居就要领钥匙了，新居金明今日很快乐，家里购置的新居就要领钥匙了，新居里有一间金明自己专用的很宽敞的房间。更让他兴奋的是，里有一间金明自己专用的很宽敞的房间。更让他兴奋的是，妈妈昨天对他说：妈妈昨天对他说：“你的房间须要购买哪些物品，怎么
9、布置，你的房间须要购买哪些物品，怎么布置，你说了算，只要不超过你说了算，只要不超过N元钱就行元钱就行”。今日一早，金明就起。今日一早，金明就起先做预算了，他把想买的物品分为两类：主件与附件，附件先做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。假如要买归类为附件的物品，必需先是从属于某个主件的。假如要买归类为附件的物品，必需先买该附件所属的主件。每个主件可以有买该附件所属的主件。每个主件可以有0个、个、1个或个或2个附件。个附件。附件不再有从属于自己的附件。金明想买的东西很多，确定附件不再有从属于自己的附件。金明想买的东西很多，确定会超过妈妈限定的会超过妈妈限定的N元。于
10、是，他把每件物品规定了一个重元。于是，他把每件物品规定了一个重要度，分为要度，分为5等：用整数等：用整数15表示，第表示，第5等最重要。他还从因等最重要。他还从因特网上查到了每件物品的价格（都是特网上查到了每件物品的价格（都是10元的整数倍）。他希元的整数倍）。他希望在不超过望在不超过N元（可以等于元（可以等于N元）的前提下，使每件物品的元）的前提下，使每件物品的价格与重要度的乘积的总和最大。价格与重要度的乘积的总和最大。设第设第j件物品的价格为件物品的价格为vj，重要度为，重要度为wj，共选中了，共选中了k件件物品，编号依次为物品，编号依次为j1，j2，jk，则所求的总和为：，则所求的总和为
11、：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是所属主件的编号）【输出文件】只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。【输入样例】1000 5800
12、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+si,2,2;11 If j+si,1,1+si,2,1fj+si,1,1+si,2,1 Then fj+si,1
13、,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分，则
14、在分，则在1分分6分之间的每一个邮资值都能得到（当然还有分之间的每一个邮资值都能得到（当然还有8分、分、9分和分和12分）；假如面值分别为分）；假如面值分别为1分、分、3分，则在分，则在1分分7分分之间的每一个邮资值都能得到。可以验证当之间的每一个邮资值都能得到。可以验证当N=3，K=2时，时，7分就是可以得到的连续的邮资最大值，所以分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为面值分别为1分、分、3分。分。【样例】【样例】INPUTN=3K=2OUTPUT13MAX=7 假如你一看到这道题目就想到搜寻，那么 这道题目就是搜索。那么为什么它出现在动态规划的专题中的？是因为 你DF
15、S生成一组邮票面值之后，你需要用某种方法把它能达到的面额都枚举出来。而这个工作如果要让枚Cnm举来做，那么太浪费资源了。枚举的复杂度是 ，尽管n、m很小，但是在大DFS的前提下就不怎么划算了。因此我们使用DP来枚举出所有可能的面额，而方法，就是传说中的完全背包（经过处理的）。Sample Problem6Sample Problem6方格取数方格取数（NOIp2000）设有设有N*N的方格图的方格图(N=10,我们将其中的某些方格我们将其中的某些方格中填入正整数中填入正整数,而其他的方格中则放入数字而其他的方格中则放入数字0。如下图所。如下图所示某人从图的左上角的示某人从图的左上角的A点动身，
16、可以向下行走，也可点动身，可以向下行走，也可以向右走，直到到达右下角的以向右走，直到到达右下角的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-
17、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,j表示走到第x步时，第1条路途走到横坐标为i的地方，第2条路
18、途走到了横坐标为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用同样的方法即可。传纸条（传纸条（NOIp2008）【问题描述】
19、【问题描述】小渊和小轩是好挚友也是同班同学，他们在一起总有小渊和小轩是好挚友也是同班同学，他们在一起总有谈不完的话题。一次素养拓展活动中，班上同学支配做成谈不完的话题。一次素养拓展活动中，班上同学支配做成一个一个m行行n列的矩阵，而小渊和小轩被支配在矩阵对角线的列的矩阵，而小渊和小轩被支配在矩阵对角线的两端，因此，他们就无法干脆交谈了。幸运的是，他们可两端，因此，他们就无法干脆交谈了。幸运的是，他们可以通过传纸条来进行沟通。纸条要经由很多同学传到对方以通过传纸条来进行沟通。纸条要经由很多同学传到对方手里，小渊坐在矩阵的左上角，坐标手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩，小轩坐在
20、矩阵的右下角，坐标阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说假如此人在小渊递给小轩纸条只会帮他们一次，也就是说假如此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。的时候帮忙，那么在小轩递给小渊的时
21、候就不会再帮忙。反之亦然。反之亦然。还有一件事情须要留意，全班每个同学情愿帮忙的好还有一件事情须要留意，全班每个同学情愿帮忙的好感度有高有低（留意：小渊和小轩的好心程度没有定义，感度有高有低（留意：小渊和小轩的好心程度没有定义，输入时用输入时用0表示），可以用一个表示），可以用一个0-100的自然数来表示，数的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到
22、这的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。样的两条路径。Sample Problem7Sample Problem7Sample Problem8Sample Problem8石子归并原题石子归并原题【题目描述】【题目描述】在一个圆形操场的四周摆放着在一个圆形操场的四周摆放着N堆石子堆石子(N=100),现现要将石子有次序地合并成一堆要将石子有次序地合并成一堆.规定每次只能选取相邻规定每次只能选取相邻的两堆合并成新的一堆的两堆合并成新的一堆,并将新的一堆的石子数并将新的一堆的石子数,记为该记为该次合并的得分次合并的得分.编一程序编一程序,由文件读入堆栈数由文件读入堆栈数
23、N及每堆栈及每堆栈的石子数的石子数(=20).选择一种合并石子的方案选择一种合并石子的方案,运用权得做运用权得做N1次合并次合并,得分的总和最小。得分的总和最小。【输入数据】【输入数据】第一行为石子堆数第一行为石子堆数N;其次行为每堆的石子数其次行为每堆的石子数,每两个数之间用一个空格每两个数之间用一个空格分隔。分隔。【输出数据】【输出数据】一行，最小总和。一行，最小总和。【输入】【输入】44594【输出】【输出】224594598总和：8913总和：2122总和：43 我们用fi,j表示以i堆石子为开头，以j堆石子为结尾的一系列石子归并起来的最小总和。因为题目中说，只能归并相邻的两堆石子。所
24、以，fi,j这一系列石子必定由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星球上，每
25、个星球上，每个Mars人都随身佩带着一串能量人都随身佩带着一串能量项链。在项链上有项链。在项链上有N颗能量珠。能量珠是一颗有头标记与颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记确定等于后一颗珠相邻的两颗珠子，前一颗珠子的尾标记确定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是子的头标记。因为只有这样，通过吸盘（吸盘是Mars人人吸取能量的一种器官）的作用，这两颗珠子才能聚合成一吸取能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸取的能量。
26、假如前一颗颗珠子，同时释放出可以被吸盘吸取的能量。假如前一颗能量珠的头标记为能量珠的头标记为m，尾标记为，尾标记为r，后一颗能量珠的头标，后一颗能量珠的头标记为记为r，尾标记为，尾标记为n，则聚合后释放的能量为（，则聚合后释放的能量为（Mars单位）单位），新产生的珠子的头标记为，新产生的珠子的头标记为m，尾标记为，尾标记为n。须要时，须要时，Mars人就用吸盘夹住相邻的两颗珠子，通人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。明显，过聚合得到能量，直到项链上只剩下一颗珠子为止。明显，不同的聚合依次得到的总能量是不同的，请你设计一个聚不同的聚合依次得到的总能量是
27、不同的，请你设计一个聚合依次，使一串项链释放出的总能量最大。合依次，使一串项链释放出的总能量最大。例如：设例如：设N=4，4颗珠子的头标记与尾标记依次为颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号。我们用记号 表示两颗珠子的表示两颗珠子的聚合操作，聚合操作，(j k)表示第表示第j，k两颗珠子聚合后所释放的能两颗珠子聚合后所释放的能量。则第量。则第4、1两颗珠子聚合后释放的能量为两颗珠子聚合后释放的能量为(4 1)=10*2*3=60。这一串项链可以得到最优值的一个聚合依次所释放的这一串项链可以得到最优值的一个聚合依次所释放的总能量为总能量为(4 1)2
28、)3）=10*2*3+10*3*5+10*5*10=710。Sample Problem10Sample Problem10乘积最大（乘积最大（NOIp2000）【问题描述】【问题描述】设有一个长度为设有一个长度为N的数字串，要求选手运用的数字串，要求选手运用K个乘号将个乘号将它分成它分成K+1个部分，找出一种分法，使得这个部分，找出一种分法，使得这K+1个部分的个部分的乘积能够为最大。乘积能够为最大。【输入】【输入】程序的输入共有两行：程序的输入共有两行：第一行共有第一行共有2个自然数个自然数N，K（6N40，1K6）其次行是一个长度为其次行是一个长度为N的数字串。的数字串。【输出】【输出】
29、输出所求得的最大乘积（一个自然数）。输出所求得的最大乘积（一个自然数）。【样例输入】【样例输入】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位转换成数字的值。对于题目中所说的具有
30、很强枚举意味的变量（如k段，n次等），一般将其放入状态中枚举。而诸如最大值最小值之类的变量，一般放入数组中作为值递推。Sample Problem11Sample Problem11统计单词个数（统计单词个数（NOIp2001）【问题描述】【问题描述】给出一个长度不超过给出一个长度不超过200的由小写英文字母组成的的由小写英文字母组成的字母串字母串(约定约定;该字串该字串以每行以每行20个字母的方式输入，且保证每行确定为个字母的方式输入，且保证每行确定为20个个)。要求将此字母串分。要求将此字母串分成成k份份(1k=40)，且每份中包含的单词个数加起来总数，且每份中包含的单词个数加起来总数最大
31、最大(每份中包含的单词可以部分重叠。当选用一个每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。单词之后，其第一个字母不能再用。例如字符串例如字符串this中可包含中可包含this和和is，选用，选用this之后就不能之后就不能包含包含th)。单词在给出。单词在给出的一个不超过的一个不超过6个单词的字典中。要求输出最大的个数。个单词的字典中。要求输出最大的个数。【样例输入】【样例输入】3thisisabookyouareaoh4isaoksab【样例输出】【样例输出】7 this /isabookyoua /reaoh 看到这道题目应当立刻有这种意识了：和乘积最大神似！所
32、以本题除了求出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。Sample Problem12Sample Problem12矩阵取数游戏（矩阵取数游戏（NOIp2007）
33、【问题描述】【问题描述】帅帅常常更同学玩一个矩阵取数游戏：对于一个给定帅帅常常更同学玩一个矩阵取数游戏：对于一个给定的的n*m的矩阵，矩阵中的每个元素的矩阵，矩阵中的每个元素aij据为非负整数。游戏据为非负整数。游戏规则如下：规则如下：1.每次取数时须从每行各取走一个元素，共每次取数时须从每行各取走一个元素，共n个。个。m次后取次后取完矩阵全部元素；完矩阵全部元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和；每每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分行取数的得分=被
34、取走的元素值被取走的元素值*2i，其中，其中i表示第表示第i次取数次取数（从（从1起先编号）；起先编号）；4.游戏结束总得分为游戏结束总得分为m次取数得分之和。次取数得分之和。帅帅想请你帮忙写个程序，对于随意矩阵，可以求出帅帅想请你帮忙写个程序，对于随意矩阵，可以求出取数后的最大得分。取数后的最大得分。【输入】【输入】第一行为两个用空格隔开的整数第一行为两个用空格隔开的整数n和和m。第第2n+1行为行为n*m矩阵，其中每行有矩阵，其中每行有m个用单个空格隔开个用单个空格隔开 【输出】【输出】一个整数，即输入矩阵取数后的最大的分。一个整数，即输入矩阵取数后的最大的分。【限制】【限制】60%的数据
35、满足：的数据满足：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+
36、ak+1*2(m-k+j-1);这道题目还要高精度，建议写好非高精的DP再修改成高精度的。过河（过河（NOIp2005）【问题描述】【问题描述】在河上有一座独木桥，一只青蛙想沿着独木桥从河在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很厌烦踩的一侧跳到另一侧。在桥上有一些石子，青蛙很厌烦踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：数轴上的一串整点：0，1，L（其中（其中L是桥的长度）是桥的长
37、度）。坐标为。坐标为0的点表示桥的起点，坐标为的点表示桥的起点，坐标为L的点表示桥的终的点表示桥的终点。青蛙从桥的起点起先，不停的向终点方向跳动。一点。青蛙从桥的起点起先，不停的向终点方向跳动。一次跳动的距离是次跳动的距离是S到到T之间的随意正整数（包括之间的随意正整数（包括S,T）。当）。当青蛙跳到或跳过坐标为青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独的点时，就算青蛙已经跳出了独木桥。木桥。题目给出独木桥的长度题目给出独木桥的长度L，青蛙跳动的距离范围，青蛙跳动的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最，桥上石子的位置。你的任务是确定青蛙要想过河，最少须要踩到的
38、石子数。少须要踩到的石子数。【输入文件】【输入文件】第一行一个正整数第一行一个正整数L（1=L=109），表示独木），表示独木桥的长度。其次行有三个正整数桥的长度。其次行有三个正整数S，T，M，分别表示青，分别表示青蛙一次跳动的最小距离，最大距离，及桥上石子的个数，蛙一次跳动的最小距离，最大距离，及桥上石子的个数，其中其中1=S=T=10，1=M fi-j+1 Then fi:=fi-j+1 Else If fifi-j Then fi:=fi-j;但是有个地方我们忽视了，那就是数据规模。L最大有109，第一个For就已经无法承受浩大的时间限制和空间限制了。所以，这种方法须要进行改进。而改进的
39、方法，就是状态压缩。我们可以发觉题目的一个玄机：虽然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
40、就可以了，因为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，比之前的困难度大大降低。这种方法叫状态压缩，我们这题用的方法叫离散化。至
41、此，过河完备AC！Sample Problem14Sample Problem14数的划分（数的划分（NOIp2001NOIp2001）【问题描述】【问题描述】将整数将整数n n分成分成k k份，且每份不能为空，随意两份不份，且每份不能为空，随意两份不能相同能相同(不考虑依次不考虑依次)。例如：。例如：n=7n=7，k=3k=3，下面三种分法被，下面三种分法被认为是相同的。认为是相同的。1 1，1 1，5;15;1，5 5，1;51;5，1 1，1;1;问有多少种不同的分法。问有多少种不同的分法。【输入】【输入】n n，k(6n=200k(6n=200，2=k=6)2=k=j Then For
42、 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及它的每个子树都有一个加分，任一棵子树subtree（
43、也包含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就是这棵树的右子树。同样的假如j是a1ai-1这棵子树的
44、根，那么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%。动态规划的核心就是“状态”和“状态转移方程”，有了这两样东西，或许还要再加点DFS、贪心、状态压缩、单调队列等来优化动态规划，
45、基本上就可以放心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