信息学奥赛中的动态规划.ppt

《信息学奥赛中的动态规划.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛中的动态规划.ppt（93页珍藏版）》请在麦多课文档分享上搜索。

1、主讲人：FireStorm,动态规划讲稿,数字三角形,IOI1994,题目描述 Description 如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。输入描述 Input Description 第一行是数塔层数N(1=N=100)。 第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。输出描述 Output Description 输出最大值。样例输入 Sample Input 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11样例输出 Sample Output 86

2、,解法1：暴搜,DFS一遍遍历整个数字三角形，对于每个节点，我们有2个选择，那么，n层的数字三角形有2n种可能，所以时间复杂度为O(2n),T L E！,解法2：贪心,一路下去只找最大的可以吗？,W A !,解法3：最长路,将整个数字三角形看作一个由点和边组成的图，以a11为起点，求它到ani(1=i=n)的最长路 Dijkstra算法：本题部分数据有负值 SPFA算法：O(kM)的话应该能行 Bellman-Ford算法：O(VE)有点危险啊 Floyd算法：O(n3)你确定要用吗？,方法可行但是打起来好麻烦,还有什么更好的算法吗？,当然有！那就是本课要讲的内容动态规划,分析这个数字三角形，

3、我们可以发现：一个节点只会受到上面两个节点的值的影响，而上面节点的值也只会受到更加上面的节点的值的影响由此可写出递归式 dpij=max(dpi-1j,dpi-1j-1)+aij 上面这个递归式在动态规划中被叫做状态转移方程式，根据这个式子，我们可以从dp11开始递推，直到数字三角形的最后一行。 时间复杂度O(n2)，完全无压力,动态规划是优美的 动态规划是神奇的 动态规划是有趣的 动态规划是简单的 动态规划是卡骗分的 动态规划是禁贪心的 动态规划是防止爆0 的 动态规划最简单最好玩了 我最喜欢动态规划了！,什么鬼！,0-1背包问题,Merkel and Hellman 1978 NOIP20

4、05普及组,题目描述 Description 由于该题目的题目描述版本过多，不再描述输入描述 Input Description 输入第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表最大重量，M代表物品的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某个物品的时间和每个物品的价值。输出描述 Output Description 输出包括一行，这一行只包含一个整数，表示在不超过规定重量的情况下，可以拿到的最大价值。样例输入 Sample Input 1 1 1 1样例输出 Sample Output 1数据范围及提示 Da

5、ta Size & Hint 【数据规模】 对于30%的数据，M=10； 对于全部的数据，M=100。,老规矩： 暴搜TLE 贪心一定WA 最短路你可以试试怎么办？,动态规划才是王道！,我们先分析下暴搜的过程： 我们对每个物品进行了搜索，产生了大量的状态，每个状态包括三个要点： 1.目前已用的背包的容量，这个不用多说 2.目前已经获得的价值，这个也不用多说 3.目前已经处理了多少物品，记录下已经处理物品数量的原因是由于每个物品只能拿一个，所以要记录下已经处理了多少物品，防止以后重复处理,有什么想法没？,为什么不记录下相同的状态时的最优策略呢？,在使用相同的容量和处理了相同的物品后，剩下的搜索过

6、程应该是相同的，假如共有n个物品，我们已经处理了m个，那么还需要处理的物品数量就是n-m，但是在背包剩余体积为v的情况下，剩下n-m个物品产生的最优解应该是相同的，这样就可以简化搜索过程，但是前面的怎么办呢？前面的当然要最好的！ 于是，我们得到一条结论： 在其他状态均相同的情况下，选择最好的总是对的！所以，我们可以开始优化这个搜索了：每次搜索到一个状态，就从之前搜到过的状态里找一遍，如果看见可以替换的状态就更新众：你不觉得更慢了么 所以，怎么办呢？,你还记的桶排序吗？直接用数组下标记录，时间复杂度O(1) 这个可以这样做吗？ 没问题！看数据范围：1=T=1000，1=M=100，状态只需要记录

7、下重量和已处理的物品数，空间复杂度O(TM)，128MB内存没问题 至于状态转移方程式的话： dpij=max(dpi-1j,dpi-1j-vi+ci) 我一般习惯写成： dpi+1j=max(dpij,dpi+1j) dpi+1j+vi=max(dpi+1j+vi,dpij+ci) 这个看个人喜好就可以了，没有强制要求的 处理时，只要for一遍，把数组填充好就可以啦，时间复杂度O(TM)P.S.：这字母是谁规定的，这么恶心,如果卡你空间怎么办？,滚蛋动数组,你还记得斐波那契问题怎么做的吗？ c=a+b a=b b=c 根本不用开一个数组嘛！ 这个问题也一样，除了前一行，其他的状态根本就用不到

8、嘛！那么：,要你何用！,也就是说，数组只留2行就可以了，每处理完一行，就把第二行的结果放回第一行，继续处理 滚动数组是用时间换空间的一种策略,有没有更好的方法呢？,背包问题可以用一维数组解决你造吗？ 由于重量没有负数，所以可以直接向后转移，而且不用向下转移了，但这样就有可能重复处理一个物品，怎么办？ 很简单，改变下方向，从后往前处理就可以啦至此，01背包完满完成,难度增加的背包问题,更加喜(sang)闻(xin)乐(bing)见(kuang)的背包问题,超大背包问题,每个物品只能拿一次，物品数量M=100，背包容量T=109，每个物品的价值=100，每个物品的重量=109,由于本题物品的价值非

9、常小，所以可以将dp数组改为由已处理的物品数量和价值，数组内存储内容改为当前所需的重量即可,二维背包问题,对于每个物品，分别有体积v和重量w，求体积和重量均不超标的情况下可以拿到的最大价值,维数改为三维，改变下转移，也可简化为二维，从后往前for得出正确答案,完全背包问题,每个物品可以拿无限次，只要不超过最大重量即可,思路1：背包+枚举,在状态转移时枚举每个物品可以拿的次数，时间复杂度O(VNK),优化1：减少物品种类,对于一个物品来说，假如它的重量大于等于另一个物品且它的价值比另一个物品低，那么要它何用？可以直接省略掉该物品，所以只要先预对所有物品进行一遍O(n2)的预处理，就能带来很大的优

10、化,优化2：转化为0-1背包,将一个物品看成多个物品，时间复杂度没有发生变化但是大家记得一个叫做鬼谷子的钱袋的题吗？如一个物品最多可以拿10个，则可以拆分成：1个该物品，2个该物品，3个该物品，4个该物品，达到log(k)的级别，也是个不错的优化,思路2：用一维背包解决,大家还记得一维的背包解决方案吗？此题也可，只不过为了使一个物品可以重复计算，只需要将从后往前改为从前往后即可，时间复杂度O(VN),多重背包问题,对于每个物品，可以拿不同的次数，如：有的1次，有的10次，有的100次,依然采取之前的二进制思想，简化问题,混合背包问题,对于一个背包问题，有多种物品可以选择：有只能拿一件的，有可以

11、拿多个的，有可以无限拿的，这时候应该怎么办？,这个问题综合了三种背包，代表这个问题可以使用各种背包问题的优化方法！,优化1,采用完全背包问题的优化方式1，即可瞬间去除大量无用物品P.S.:简直就是个垃圾清理器,优化2,先不考虑多重背包，只考虑01背包和完全背包，那么，就可以用喜闻乐见的一维数组方法求解，只要在转移前判断下是从前往后还是从后往前转移就行了，那么多重背包怎么办？笨！用二进制转成多个01背包啊！,金明的预算方案(NOIP2006提高组),题目描述 Description 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说

12、：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，右图就是一些主件与附件的例子。 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为

13、vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。,输入描述 Input Description 第1行，为两个正整数，用一个空格隔开： N m （其中N（0，表示该物品为附件，q是所属主件的编号） 输出描述 Output Description 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(200000) 样例输入 Sample Input 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2

14、 0 样例输出 Sample Output 2200 数据范围及提示 Data Size & Hint 无,对于每个主件，它最多有2个附件，那么每个物品只有这几种情况： 1.不带附件 2.带附件A 3.带附件B 4.带附件A和B 5.连主件都不拿 那么只要在状态转移时枚举每个物品拿还是不拿，拿几个附件即可,不过好好看看还是能发现些什么的：,这题放眼望去应该是个树形dp，好可怕的说,至此，背包问题全部完成！,但这仅仅是简单的背包问题而已,区间型DP,别看我看标题,石子归并,经典区间型dp,题目描述 Description 有n堆石子排成一列，每堆石子有一个重量wi, 每次合并可以合并相邻的两堆石

15、子，一次合并的代价为两堆石子的重量和wi+wi+1。问安排怎样的合并顺序，能够使得总合并代价达到最小。输入描述 Input Description 第一行一个整数n（n=100） 第二行n个整数w1,w2.wn (wi = 100)输出描述 Output Description 一个整数表示最小合并代价样例输入 Sample Input 4 4 1 1 4样例输出 Sample Output 18数据范围及提示 Data Size & Hint 无,分析下花费吧,花费是由两堆石子组成的，即： costij=wi+wi+1+wj-1+wj要合并i-j堆，必须要先合并ik堆和k+1j堆，可以得出递

16、推式js(i,j)= wi i=jmin( js(i,i) + js(i+1,j) js(i,j-1) + js(j,j) )+costij ij,然后怎么办？递归处理吗？,我说你百分百超时你信吗？ 这节课学的啥？动态规划啊！开个数组，记录下来，直接转成递推，时间复杂度O(n2)，完全无压力P.S.:这个题写代码还是稍微有点难度的，所以写不出来的童鞋可以考虑放(mei)弃(tian)本(yi)题(bian),能量项链(noip2006),题目描述 Description 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记

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

18、子的头标记与尾标记依次为(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输出描述 Output Description 只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。样例输入 Sample Input 42 3 5 10样例输出 Sam

19、ple Output 710数据范围及提示 Data Size & Hint 无,众所皆知，丝带项链是环形的，也就是说，这个题相比起石子归并问题来说，变成了环形摆放，怎么办呢poi？,用脑子想一想，可以想出：即使是一个环合并，也不会合并超过2圈 也就是说，可以把这串项链看作2倍长，读入时就进行预处理，之后合并时只要找出在其中一点断开能得到的项链的最大能量值就可以了,乘积最大,NOIP2000,题目描述 Description 今年是国际数学联盟确定的“2000世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好

20、朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。输入描述 Input Description 程序的输入共有两行： 第一行共有2个自然数N，K（6N40，1K6） 第二行是一个长

21、度为N的数字串。,输出描述 Output Description结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。样例输入 Sample Input 4 2 1231样例输出 Sample Output 62数据范围及提示 Data Size & Hint 本题由于比较老，数据实际也比较小，用long long 即可通过,这个题目要求用指定的乘号数量分开一个数，将它变得尽可能大，先找递推式： aijk=max(aiik-1*ai+1jk-1aij-1k-1*ajjk-1)aijk的含义为：从i到j段，使用了k个乘号所产生的最大乘积，还可以简化为aik，含义为从1到i段使用了k

22、个乘号所产生的最大乘积记录到dp数组里进行动态规划就好了,数的划分(NOIP2001),题目描述 Description 将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。 例如：n=7，k=3，下面三种划分方案被认为是相同的。 1 1 51 5 15 1 1 问有多少种不同的分法。,输入描述 Input Description 输入：n，k (6n=200，2=k=6)输出描述 Output Description 输出：一个整数，即不同的分法。样例输入 Sample Input7 3样例输出 Sample Output 4数据范围及提示 Data Size ,这个题

23、目需要让人感到猎奇( 不要想歪)的动态规划：对于一个数的划分方式，我们可以分为两种： 1.划分的结果中有数字1的 2.划分的结果中没有数字1的对于会产生数字1的划分结果，我们可以忽略掉那个1，那么，n划分成m部分有多少种方法等于n-1划分成m-1部分有多少种方法，对于不产生数字1的划分结果，我们有另一种巧妙的办法：所有划分产生的数字统一减1，那么， n划分成m部分有多少种方法等于n-m划分成m部分有多少种方法dpij=dpi-1j-1+dpi-jj,总的来说，区间型dp要比背包型dp难一些，所以下面来点简单的dp,序列型dp,传说中最水的dp,最长上升子序列,题目描述 Description

24、给一个数组a1, a2 . an，找到最长的上升降子序列ab1ab2 abk，其中b1b2bk。 输出长度即可。输入描述 Input Description 第一行，一个整数N。 第二行 ，N个整数（N = 5000）输出描述 Output Description 输出K的极大值，即最长不下降子序列的长度,样例输入 Sample Input 5 9 3 6 2 7样例输出 Sample Output 3数据范围及提示 Data Size & Hint 【样例解释】 最长不下降子序列为3,6,7,这题还用讲么？,RT,我的做法是开一个dp数组，记录下以该数字为开头且带有该数字的最长上升子序列的长

25、度，应该没有和我一样的,合唱队形(NOIP2004),题目描述 DescriptionN位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1Ti+1TK(1=i=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入描述 Input Description 输入文件chorus.in的第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(1

26、30=Ti=230)是第i位同学的身高(厘米)。输出描述 Output Description 输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。,样例输入 Sample Input 8 186 186 150 200 160 130 197 220样例输出 Sample Output 4数据范围及提示 Data Size & Hint 对于50的数据，保证有n=20； 对于全部的数据，保证有n=100。,算法1,这道题要求百摆成合唱队形，即前面一段单调递增，后面一段单调下降的序列于是就有了算法1：枚举队伍中的最高点，前后的队伍分别求最长上升子序列和最长下降

27、子序列，时间复杂度O(n*2*n2)=O(n3)虽然不超时，但是敲起代码来有点麻烦额,算法2：,既然要枚举每一个点，不如直接求出以每个点为开头或结尾的最长上升和最长下降子序列，然后直接for一遍找出二者相加的最大值再减去1(因为队伍只有一个最高点)即可代码简化了不少，而且时间复杂度压到了O(n2)！,大家都知道最长公共子序列和最长严格上升子序列吧都是大水题吧,总有些不好的预感额,但是如果将两者结合起来呢？ 那就是LCIS(Longest Common Increasing Subsequence)最长公共严格上升子序列！,果然来了,题目描述 Description 熊大妈的奶牛在小沐沐的熏陶下

28、开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。 小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。 奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。输入描述 Input Description 第一行N，表示A，B的长度。 第二行，串A。 第三行，串B。输出描述 Output Description 输出长度。,样例输入 Sample Inpu

29、t 4 2 2 1 3 2 1 2 3样例输出 Sample Output 2数据范围及提示 Data Size & Hint 1=N=3000，A，B中的数字不超过maxlongint,这题说实话我也不大会,不过我还得硬着头皮讲,好吧正题开始：dpij表示a串前i个数和b串前j个数且以b串第j个数结尾的最长公共严格上升子序列(好绕口以后就叫LCIS了)LCIS的长度，然后根据最长公共子序列一题的状态转移方程式可以得出本题的状态转移方程式：dpij=dpi-1j (ai!=bj)dpij=max(dpi-1k)+1 (ai=bj&akbj)应该不是很难懂填充dp数组不用我教了吧恭喜各位完成序列

30、型dp,棋盘型dp,最终boss前的最后一个dp,过河卒,A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 P8 和 C）。卒不能通过对方马的控制点。 棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C不等于A，同时C不等于B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 1=n,m=15,大水题一枚,

31、水水就过了呗,卒走到一个格子的方式只有两种： 1.从它左边的格子过来 2.从它上面的格子过来那么，走到这个格子的方法数=走到上面格子的方法数+走到左边格子的方法数,骑士游历,题目描述 Description 设有一个n*m的棋盘（2n50，2m50），如下图，在棋盘上有一个中国象棋马。 规定： 1)马只能走日字 2)马只能向右跳 问给定起点x1,y1和终点x2,y2，求出马从x1,y1出发到x2,y2的合法路径条数。输入描述 Input Description 第一行2个整数n和m 第二行4个整数x1,y1,x2,y2输出描述 Output Description 输出方案数样例输入 Samp

32、le Input 30 30 1 15 3 15样例输出 Sample Output 2数据范围及提示 Data Size & Hint 2=n,m=50,NOIP1997,和过河卒有什么区别额,不就是改改状态转移方程式啊 这个还不会的话还要不要来Loi啊,传纸条(NOIP2008),题目描述 Description 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标

33、(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两

34、条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。输入描述 Input Description 输入的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1=m,n=50）。 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。,输出描述 Output Description 输出共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。样例输入 Sample Input 3 3 0 3 9 2 8 5 5 7 0样例输出 Sample Output 34数据范围及提示 Da

35、ta Size & Hint 30%的数据满足：1=m,n=10 100%的数据满足：1=m,n=50,大家有什么想法呢？,首先，我们可以轻松的得到一个错误的算法：跑两遍数字三角形，很明显这个算法是错误的：因为有可能出现重复的路径，那么，这个算法就没用了吗？,当然不是的！我们这个算法的想法是：先找出好心值最高的路径，然后归零，找好心值次高的路径，但是这样会导致出现重复路径，那么我们稍微改一下这个算法：让两人同时找好心值最高的路径 那不就乱套了了吗？！,所以，我们要改一下这个方法：让两人同时从左上角到右下角走，这样的话只要两人不走到同一个格子上(起点和终点除外)，那么这条路径就是可行的！,dpi

36、jkl分别记录纸条A和纸条B所在的位置，转移时考虑4种情况： 1.A纸条向右，B纸条也向右 2.A纸条向右，B纸条向下 3.A纸条向下，B纸条也向下 4.A纸条向下，B纸条向右,可是还能再优化不是吗？,由于两张纸条移动的格子数是相同的，所以他们一定在同一条斜线上，所以dp数组优化到三维：i,j,k分别表示走过的格子数，纸条A所在的行，纸条B所在的行，这样，三维数组就可以表示出状态来，而且还减去了许多无用的状态,最終鬼畜道化師M【】 树形dp&状压DP&DP骗分 (仅简单讲解),树形dp,顾名思义，在树上进行的DP 郑州学习时应该有讲过由于这一部分的题目我也不太会，所以每一部分只讲一题,没有上司

37、的舞会,题目描述 DescriptionUral大学有N个职员，编号为1N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。输入描述 Input Description 第一行一个整数N。(1=N=6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128=Ri=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。输出描述 Output Description 输出最大的快乐指数。,样例输入 S

38、ample Input 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0样例输出 Sample Output5,嘛，这也是道很经典的树形dp题目了,这道题的评级是Diamond钻石 ，怎么看也不是noip提高难度的题 不过我还是得讲对于一个职员来说，他只有两种状态：参加，不参加；有些人是不是想到状压那边去了看本题数据范围啊！6000啊！那么，这题是不是就不可解了呢？,当然可以解！,不然为啥要出这道题 对于一个职员来说，他要么来，要么不来，如果他来，那么他的下属就一个都不敢来(这是废话，如果你的班主任天天去逛银座，那么你还敢去银座吗？) 于是，我们可以这样做

39、：为啥到了关键时候就翻页,开数组dp60002，dpi0代表i号职员不来时能得到的快乐值，dpi1则代表i号职员来时能得到的最大快乐值 当这个人不来时，对他的下属是没有影响的，或者说，他的下属爱来来，不爱来不来所以可得：dpi0=max(dpk0,dpk1)，这里的k代表他的所有下属。因为他不来，他的下属来不来都行，而且对他的上司又没有影响，所以我们可以贪心的找最大的； dpi1=dpk0+ai，k依然代表他的所有下属。如果他来了，那么他的下属就都不能来，所以就是他的下属全都不来的最大快乐值加上他的快乐值。 这样就好做了 DFS一遍求出所有人的快乐值，可以证明，最后产生的图形一定是一棵树，所以

40、，只要最后找出这个公司的超级大BOSS，并且找出他来和不来两个状态快乐值最大的那个，这个题就AC啦P.S.:简直累人,状压dpTSP问题,旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 这个有点难懂额 没关系，codevs上就有这个题！,题目描述 Description 有一个送外卖的，他手上有n份订单，他要把n份东西，分别

41、送达n个不同的客户的手上。n个不同的客户分别在1n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。输入描述 Input Description 第一行一个正整数n （1=n=15） 接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同，也就是说道路都是单向的。输出描述 Output Description

42、 一个正整数表示最少花费的时间,样例输入 Sample Input 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0样例输出 Sample Output 8数据范围及提示 Data Size & Hint 1=n=15,这个题有什么特点呢？,这个题的特点是：N特别小！ 当然，N如果不小的话状压是做不了的状压的题目数据一般不会超过15，一会儿你就知道这是为什么了,对于这个题，我们有什么办法呢？,没什么办法，只能枚举这个高中不好好上，考不上大学，长大了只能送外卖的倒霉孩子经过了哪几个城市来进行状态转移，反正一个城市只有两种状态：经过和没有经过，那么，有没有想起和刚才那

43、题一样的地方？ 开15维数组记录下每个城市是否经过了！ 笨！ 15维数组我看你怎么维护！ 既然已经压成二进制数了，为什么不再转成十进制数来开数组呢？ 没错，这就是状压dp的数据特别小的原因！,此题无节操,开数组dp6553616，dpij的含义是，经过了！#￥%&*城市，目前处于第j个城市时走过的最短距离最后需要求的是经过了所有的城市后回到第一个城市时的最短距离代码实现的话用位运算吧,地鼠游戏,题目描述 Description王钢是(此处略去一些无用信息) 地鼠游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时，会在地板上一下子冒出很多地鼠来，然后等你用榔头去敲击这些地鼠，每个地鼠被敲击后，

44、将会增加相应的游戏分值。问题是这些地鼠不会傻傻地等你去敲击，它总会在冒出一会时间后又钻到地板下面去（而且再也不上来），每个地鼠冒出后停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同，为了胜出，游戏参与者就必须根据每个地鼠的特性，有选择地尽快敲击一些地鼠，使得总的得分最大。 这个极具挑战性的游戏王钢特别喜欢，最近他经常在星期天上午玩这个游戏，慢慢地他不但敲击速度越来越快（敲击每个地鼠所需要的耗时是1秒），而且他还发现了游戏的一些特征，那就是每次游戏重新开始后，某个地鼠冒出来后停留的时间都是固定的，而且他记录了每个地鼠被敲击后将会增加的分值。于是，他在每次游戏开始后总能有次序

45、地选择敲击不同的地鼠，保证每次得到最大的总分值。 输入描述 Input Description 输入包含3行，第一行包含一个整数n（1=n=100）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间，第三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值（=100）。每行中第i个数都表示第i个地鼠的信息。 输出描述 Output Description 输出只有一行一个整数，表示王钢所能获得的最大游戏总分值。 样例输入 Sample Input 5 5 3 6 1 4 7 9 2 1 5 样例输出 Sample Output 24,这个题是用DP骗过去的,R

46、T，原版的数据范围是200000，正解是贪心+堆，时间复杂度O(NlogN)但是dp只能做到O(n2)不过，这是codevs嘛，这数据简直太良心啦hhh,开二维dp数组，dpij是在第i只地鼠，时间已过去j秒时可以拿到的最大得分，开始先排遍序，然后像背包一样转移就行啦,对于有些题目来说，dp可能不是正解，但是，dp可以骗分，有些题的数据就是30%暴力，60%DP，100%正解，dp全对的题也是noip每年必考的内容，所以，学好DP，对大家的帮助是非常大的,终于讲完了！,那么，DP部分就告一段落吧，喜欢刷(zi)题(nve)的同(dou)学(M)如果需要题目的话，我会给你找一些喜(jie)闻(cao)乐(sang)见(shi)的题目的！,