信息学奥赛中的动态规划教学课件

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

2、63题目描述 Description 3解法1：暴搜DFS一遍遍历整个数字三角形，对于每个节点，我们有2个选择，那么，n层的数字三角形有2n种可能，所以时间复杂度为O(2n)T L E！4解法1：暴搜DFS一遍遍历整个数字三角形，对于每个节点，我们解法2：贪心一路下去只找最大的可以吗？W A !5解法2：贪心一路下去只找最大的可以吗？W A !5解法3：最长路将整个数字三角形看作一个由点和边组成的图，以a11为起点，求它到ani(1=i=n)的最长路Dijkstra算法：本题部分数据有负值SPFA算法：O(kM)的话应该能行Bellman-Ford算法：O(VE)有点危险啊Floyd算法：O(

3、n3)你确定要用吗？方法可行但是打起来好麻烦6解法3：最长路将整个数字三角形看作一个由点和边组成的图，以a还有什么更好的算法吗？当然有！那就是本课要讲的内容动态规划7还有什么更好的算法吗？当然有！那就是本课要讲的内容动态规分析这个数字三角形，我们可以发现：一个节点只会受到上面两个节点的值的影响，而上面节点的值也只会受到更加上面的节点的值的影响由此可写出递归式dpij=max(dpi-1j,dpi-1j-1)+aij上面这个递归式在动态规划中被叫做状态转移方程式，根据这个式子，我们可以从dp11开始递推，直到数字三角形的最后一行。时间复杂度O(n2)，完全无压力8分析这个数字三角形，我们可以发现

4、：一个节点只会受到上面两个节动态规划是优美的动态规划是神奇的动态规划是有趣的动态规划是简单的动态规划是卡骗分的动态规划是禁贪心的动态规划是防止爆0 的动态规划最简单最好玩了我最喜欢动态规划了！什么鬼！9动态规划是优美的什么鬼！90-1背包问题Merkel and Hellman 1978NOIP2005普及组100-1背包问题Merkel and Hellman 19题目描述 Description 由于该题目的题目描述版本过多，不再描述输入描述 Input Description 输入第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表最大重量，M代表物品的数

5、目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某个物品的时间和每个物品的价值。输出描述 Output Description 输出包括一行，这一行只包含一个整数，表示在不超过规定重量的情况下，可以拿到的最大价值。样例输入 Sample Input 1 11 1样例输出 Sample Output 1数据范围及提示 Data Size & Hint 【数据规模】对于30%的数据，M=10；对于全部的数据，M=100。11题目描述 Description 11老规矩：暴搜TLE贪心一定WA最短路你可以试试怎么办？12老规矩：12动态规划才是王道！我们先分析下暴搜

6、的过程：我们对每个物品进行了搜索，产生了大量的状态，每个状态包括三个要点：1.目前已用的背包的容量，这个不用多说2.目前已经获得的价值，这个也不用多说3.目前已经处理了多少物品，记录下已经处理物品数量的原因是由于每个物品只能拿一个，所以要记录下已经处理了多少物品，防止以后重复处理有什么想法没？13动态规划才是王道！我们先分析下暴搜的过程：有什么想法没？13为什么不记录下相同的状态时的最优策略呢？14为什么不记录下相同的状态时的最优策略呢？14在使用相同的容量和处理了相同的物品后，剩下的搜索过程应该是相同的，假如共有n个物品，我们已经处理了m个，那么还需要处理的物品数量就是n-m，但是在背包剩余

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

8、MB内存没问题至于状态转移方程式的话：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.：这字母是谁规定的，这么恶心16你还记的桶排序吗？直接用数组下标记录，时间复杂度O(1)16如果卡你空间怎么办？17如果卡你空间怎么办？17滚蛋动数组你还记得斐波那契问题怎么做的吗？c=a+b a=b b=c根本不用开一个数组嘛！这个问题也一样，除了前一行，其他的状

9、态根本就用不到嘛！那么：要你何用！18滚蛋动数组你还记得斐波那契问题怎么做的吗？要你何用！18也就是说，数组只留2行就可以了，每处理完一行，就把第二行的结果放回第一行，继续处理滚动数组是用时间换空间的一种策略有没有更好的方法呢？19也就是说，数组只留2行就可以了，每处理完一行，就把第二行的结背包问题可以用一维数组解决你造吗？由于重量没有负数，所以可以直接向后转移，而且不用向下转移了，但这样就有可能重复处理一个物品，怎么办？很简单，改变下方向，从后往前处理就可以啦至此，01背包完满完成20背包问题可以用一维数组解决你造吗？20难度增加的背包问题更加喜(sang)闻(xin)乐(bing)见(ku

10、ang)的背包问题21难度增加的背包问题更加喜(sang)闻(xin)乐(bing超大背包问题每个物品只能拿一次，物品数量M=100，背包容量T=109，每个物品的价值=100，每个物品的重量=109由于本题物品的价值非常小，所以可以将dp数组改为由已处理的物品数量和价值，数组内存储内容改为当前所需的重量即可22超大背包问题每个物品只能拿一次，物品数量M=100，背包容二维背包问题对于每个物品，分别有体积v和重量w，求体积和重量均不超标的情况下可以拿到的最大价值维数改为三维，改变下转移，也可简化为二维，从后往前for得出正确答案23二维背包问题对于每个物品，分别有体积v和重量w，求体积和重量完

11、全背包问题每个物品可以拿无限次，只要不超过最大重量即可24完全背包问题每个物品可以拿无限次，只要不超过最大重量即可24思路1：背包+枚举在状态转移时枚举每个物品可以拿的次数，时间复杂度O(VNK)25思路1：背包+枚举在状态转移时枚举每个物品可以拿的次数，时间优化1：减少物品种类对于一个物品来说，假如它的重量大于等于另一个物品且它的价值比另一个物品低，那么要它何用？可以直接省略掉该物品，所以只要先预对所有物品进行一遍O(n2)的预处理，就能带来很大的优化26优化1：减少物品种类对于一个物品来说，假如它的重量大于等于另优化2：转化为0-1背包将一个物品看成多个物品，时间复杂度没有发生变化但是大家

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

13、次数，如：有的1次，有混合背包问题对于一个背包问题，有多种物品可以选择：有只能拿一件的，有可以拿多个的，有可以无限拿的，这时候应该怎么办？30混合背包问题对于一个背包问题，有多种物品可以选择：有只能拿一这个问题综合了三种背包，代表这个问题可以使用各种背包问题的优化方法！31这个问题综合了三种背包，代表这个问题可以使用各种背包问题的优优化1采用完全背包问题的优化方式1，即可瞬间去除大量无用物品P.S.:简直就是个垃圾清理器32优化1采用完全背包问题的优化方式1，即可瞬间去除大量无用物品优化2先不考虑多重背包，只考虑01背包和完全背包，那么，就可以用喜闻乐见的一维数组方法求解，只要在转移前判断下是

14、从前往后还是从后往前转移就行了，那么多重背包怎么办？笨！用二进制转成多个01背包啊！33优化2先不考虑多重背包，只考虑01背包和完全背包，那么，就可金明的预算方案(NOIP2006提高组)主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无题目描述 Description 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，右图就是一些主件与附件的例子。如果要买归类为

15、附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。34金明的预算方案(NO

16、IP2006提高组)主件附件电脑打印机，输入描述 Input Description 第1行，为两个正整数，用一个空格隔开：N m（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q（其中v表示该物品的价格（v0，表示该物品为附件，q是所属主件的编号）输出描述 Output Description 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(200000)样例输入 Sample Input 1000 5800 2 0 400 5 1300 5 1400 3 05

17、00 2 0样例输出 Sample Output 2200数据范围及提示 Data Size & Hint 无35输入描述 Input Description 35对于每个主件，它最多有2个附件，那么每个物品只有这几种情况：1.不带附件2.带附件A3.带附件B4.带附件A和B5.连主件都不拿那么只要在状态转移时枚举每个物品拿还是不拿，拿几个附件即可不过好好看看还是能发现些什么的：这题放眼望去应该是个树形dp，好可怕的说36对于每个主件，它最多有2个附件，那么每个物品只有这几种情况：至此，背包问题全部完成！但这仅仅是简单的背包问题而已37至此，背包问题全部完成！但这仅仅是简单的背包问题而已37区

18、间型DP别看我看标题38区间型DP别看我看标题38石子归并经典区间型dp39石子归并经典区间型dp39题目描述 Description有n堆石子排成一列，每堆石子有一个重量wi, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和wi+wi+1。问安排怎样的合并顺序，能够使得总合并代价达到最小。输入描述 Input Description第一行一个整数n（n=100）第二行n个整数w1,w2.wn (wi = 100)输出描述 Output Description一个整数表示最小合并代价样例输入 Sample Input44 1 1 4样例输出 Sample Output18数据

19、范围及提示 Data Size & Hint无40题目描述 Description40分析下花费吧花费是由两堆石子组成的，即：costij=wi+wi+1+wj-1+wj要合并i-j堆，必须要先合并ik堆和k+1j堆，可以得出递推式 js(i,j)= wi i=j min( js(i,i) + js(i+1,j) js(i,j-1) + js(j,j) )+costijij41分析下花费吧花费是由两堆石子组成的，即：41然后怎么办？递归处理吗？我说你百分百超时你信吗？这节课学的啥？动态规划啊！开个数组，记录下来，直接转成递推，时间复杂度O(n2)，完全无压力P.S.:这个题写代码还是稍微有点难

20、度的，所以写不出来的童鞋可以考虑放(mei)弃(tian)本(yi)题(bian)42然后怎么办？递归处理吗？我说你百分百超时你信吗？42能量项链(noip2006)题目描述 Description在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头

21、标记为r，尾标记为n，则聚合后释放的能量为m*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暂时找不到能量项链这种高级玩意儿，拿这个代替下吧43能量项

22、链(noip2006)题目描述 Description这一串项链可以得到最优值的一个聚合顺序所释放的总能量为(41)2)3）=10*2*3+10*3*5+10*5*10=710输出描述 Output Description只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。样例输入 Sample Input42 3 5 10样例输出 Sample Output710数据范围及提示 Data Size & Hint无44这一串项链可以得到最优值的一个聚合顺序所释放的总能量为44众所皆知，丝带项链是环形的，也就是说，这个题相比起石子归并问题来说，变成了环形摆放，怎么办呢

23、poi？用脑子想一想，可以想出：即使是一个环合并，也不会合并超过2圈也就是说，可以把这串项链看作2倍长，读入时就进行预处理，之后合并时只要找出在其中一点断开能得到的项链的最大能量值就可以了45众所皆知，丝带项链是环形的，也就是说，这个题相比起石子归并问乘积最大NOIP200046乘积最大NOIP200046题目描述 Description今年是国际数学联盟确定的“2000世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为

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

25、结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。样例输入 Sample Input4 21231样例输出 Sample Output62数据范围及提示 Data Size & Hint本题由于比较老，数据实际也比较小，用long long 即可通过4848这个题目要求用指定的乘号数量分开一个数，将它变得尽可能大，先找递推式：aijk=max(aiik-1*ai+1jk-1aij-1k-1*ajjk-1)aijk的含义为：从i到j段，使用了k个乘号所产生的最大乘积，还可以简化为aik，含义为从1到i段使用了k个乘号所产生的最大乘积记录到dp数组里进行动态规划就好了49这个题目

26、要求用指定的乘号数量分开一个数，将它变得尽可能大，先数的划分(NOIP2001)题目描述 Description将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。例如：n=7，k=3，下面三种划分方案被认为是相同的。1 1 51 5 15 1 1问有多少种不同的分法。50数的划分(NOIP2001)题目描述 Description输入描述 Input Description输入：n，k (6n=200，2=k=6)输出描述 Output Description输出：一个整数，即不同的分法。样例输入 Sample Input 7 3样例输出 Sample Output4数

27、据范围及提示 Data Size & Hint 四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;51输入描述 Input Description51这个题目需要让人感到猎奇( 不要想歪)的动态规划：对于一个数的划分方式，我们可以分为两种：1.划分的结果中有数字1的2.划分的结果中没有数字1的对于会产生数字1的划分结果，我们可以忽略掉那个1，那么，n划分成m部分有多少种方法等于n-1划分成m-1部分有多少种方法，对于不产生数字1的划分结果，我们有另一种巧妙的办法：所有划分产生的数字统一减1，那么， n划分成m部分有多少种方法等于n-m划分成m部分有多少种方法dpij=dpi-1j-1

28、+dpi-jj52这个题目需要让人感到猎奇( 不要想歪)的动态规划：52总的来说，区间型dp要比背包型dp难一些，所以下面来点简单的dp53总的来说，区间型dp要比背包型dp难一些，所以下面来点简单序列型dp传说中最水的dp54序列型dp传说中最水的dp54最长上升子序列题目描述 Description给一个数组a1, a2 . an，找到最长的上升降子序列ab1ab2 . abk，其中b1b2.bk。输出长度即可。输入描述 Input Description第一行，一个整数N。第二行 ，N个整数（N = 5000）输出描述 Output Description输出K的极大值，即最长不下降子序

29、列的长度样例输入 Sample Input59 3 6 2 7样例输出 Sample Output3数据范围及提示 Data Size & Hint【样例解释】最长不下降子序列为3,6,755最长上升子序列题目描述 Description样例输入 Sa这题还用讲么？RT我的做法是开一个dp数组，记录下以该数字为开头且带有该数字的最长上升子序列的长度，应该没有和我一样的56这题还用讲么？RT我的做法是开一个dp数组，记录下以该数字为合唱队形(NOIP2004)题目描述 Description N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指

30、这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1.Ti+1TK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入描述 Input Description输入文件chorus.in的第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。输出描述 Output Description输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。57合唱队

31、形(NOIP2004)题目描述 Description样例输入 Sample Input8186 186 150 200 160 130 197 220样例输出 Sample Output4数据范围及提示 Data Size & Hint对于50的数据，保证有n=20；对于全部的数据，保证有n=100。58样例输入 Sample Input58算法1这道题要求百摆成合唱队形，即前面一段单调递增，后面一段单调下降的序列于是就有了算法1：枚举队伍中的最高点，前后的队伍分别求最长上升子序列和最长下降子序列，时间复杂度O(n*2*n2)=O(n3)虽然不超时，但是敲起代码来有点麻烦额59算法1这道题要

32、求百摆成合唱队形，即前面一段单调递增，后面一算法2：既然要枚举每一个点，不如直接求出以每个点为开头或结尾的最长上升和最长下降子序列，然后直接for一遍找出二者相加的最大值再减去1(因为队伍只有一个最高点)即可代码简化了不少，而且时间复杂度压到了O(n2)！60算法2：既然要枚举每一个点，不如直接求出以每个点为开头或结尾大家都知道最长公共子序列和最长严格上升子序列吧都是大水题吧总有些不好的预感额61大家都知道最长公共子序列和最长严格上升子序列吧都是大水题吧但是如果将两者结合起来呢？那就是LCIS(Longest Common Increasing Subsequence)最长公共严格上升子序列！

33、果然来了62但是如果将两者结合起来呢？那就是LCIS(Longest 题目描述 Description熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。输入描述 Input Description第一行N，表示A，B的长度。

34、第二行，串A。第三行，串B。输出描述 Output Description输出长度。63题目描述 Description63样例输入 Sample Input42 2 1 32 1 2 3样例输出 Sample Output2数据范围及提示 Data Size & Hint1=N=3000，A，B中的数字不超过maxlongint64样例输入 Sample Input64这题说实话我也不大会不过我还得硬着头皮讲好吧正题开始：dpij表示a串前i个数和b串前j个数且以b串第j个数结尾的最长公共严格上升子序列(好绕口以后就叫LCIS了)LCIS的长度，然后根据最长公共子序列一题的状态转移方程式可以

35、得出本题的状态转移方程式： dpij=dpi-1j (ai!=bj) dpij=max(dpi-1k)+1 (ai=bj&akbj)应该不是很难懂填充dp数组不用我教了吧恭喜各位完成序列型dp65这题说实话我也不大会不过我还得硬着头皮讲好吧正题开始棋盘型dp最终boss前的最后一个dp66棋盘型dp最终boss前的最后一个dp66过河卒A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 P8 和 C）。卒不能

36、通过对方马的控制点。棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C不等于A，同时C不等于B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。1=n,m=15大水题一枚67过河卒A 点有一个过河卒，需要走到目标 B 点。卒行走规则：水水就过了呗卒走到一个格子的方式只有两种：1.从它左边的格子过来2.从它上面的格子过来那么，走到这个格子的方法数=走到上面格子的方法数+走到左边格子的方法数68水水就过了呗卒走到一个格子的方式只有两种：68骑士游历题目描述 Description 设有一个n*m的

37、棋盘（2n50，2m50），如下图，在棋盘上有一个中国象棋马。规定：1)马只能走日字2)马只能向右跳问给定起点x1,y1和终点x2,y2，求出马从x1,y1出发到x2,y2的合法路径条数。 输入描述 Input Description 第一行2个整数n和m第二行4个整数x1,y1,x2,y2输出描述 Output Description 输出方案数样例输入 Sample Input 30 301 15 3 15样例输出 Sample Output 2数据范围及提示 Data Size & Hint 2=n,m=50NOIP199769骑士游历题目描述 Description NOIP19976

38、和过河卒有什么区别额不就是改改状态转移方程式啊这个还不会的话还要不要来Loi啊70和过河卒有什么区别额不就是改改状态转移方程式啊70传纸条(NOIP2008)题目描述 Description小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向

39、左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。输入描述 Input Description输入的第一行有

40、2个用空格隔开的整数m和n，表示班里有m行n列（1=m,n=50）。接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。71传纸条(NOIP2008)题目描述 Description7输出描述 Output Description输出共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。样例输入 Sample Input3 30 3 92 8 55 7 0样例输出 Sample Output34数据范围及提示 Data Size & Hint30%的数据满足：1=m,n=10100%的数据满足：1=m

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

42、pijkl分别记录纸条A和纸条B所在的位置，转移时考虑4种情况：1.A纸条向右，B纸条也向右2.A纸条向右，B纸条向下3.A纸条向下，B纸条也向下4.A纸条向下，B纸条向右74首先，我们可以轻松的得到一个错误的算法：跑两遍数字三角形，很可是还能再优化不是吗？由于两张纸条移动的格子数是相同的，所以他们一定在同一条斜线上，所以dp数组优化到三维：i,j,k分别表示走过的格子数，纸条A所在的行，纸条B所在的行，这样，三维数组就可以表示出状态来，而且还减去了许多无用的状态75可是还能再优化不是吗？由于两张纸条移动的格子数是相同的，所以最終鬼畜道化師M【】树形dp&状压DP&DP骗分 (仅简单讲解)76

43、最終鬼畜道化師M【】树形dp&状树形dp顾名思义，在树上进行的DP郑州学习时应该有讲过由于这一部分的题目我也不太会，所以每一部分只讲一题77树形dp顾名思义，在树上进行的DP77没有上司的舞会题目描述 Description Ural大学有N个职员，编号为1N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。输入描述 Input Description第一行一个整数N。(1=N=6000)接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128=

44、Ri=127)接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。最后一行输入0,0。输出描述 Output Description输出最大的快乐指数。78没有上司的舞会78样例输入 Sample Input71 1 1 1 1 1 11 32 36 47 44 53 50 0样例输出 Sample Output579样例输入 Sample Input79嘛，这也是道很经典的树形dp题目了这道题的评级是Diamond钻石 ，怎么看也不是noip提高难度的题 不过我还是得讲对于一个职员来说，他只有两种状态：参加，不参加；有些人是不是想到状压那边去了看本题数据范围啊！6000啊！那么，这

45、题是不是就不可解了呢？80嘛，这也是道很经典的树形dp题目了这道题的评级是Diamon当然可以解！不然为啥要出这道题对于一个职员来说，他要么来，要么不来，如果他来，那么他的下属就一个都不敢来(这是废话，如果你的班主任天天去逛银座，那么你还敢去银座吗？)于是，我们可以这样做：为啥到了关键时候就翻页81当然可以解！不然为啥要出这道题81开数组dp60002，dpi0代表i号职员不来时能得到的快乐值，dpi1则代表i号职员来时能得到的最大快乐值当这个人不来时，对他的下属是没有影响的，或者说，他的下属爱来来，不爱来不来所以可得：dpi0=max(dpk0,dpk1)，这里的k代表他的所有下属。因为他不

46、来，他的下属来不来都行，而且对他的上司又没有影响，所以我们可以贪心的找最大的；dpi1=dpk0+ai，k依然代表他的所有下属。如果他来了，那么他的下属就都不能来，所以就是他的下属全都不来的最大快乐值加上他的快乐值。这样就好做了DFS一遍求出所有人的快乐值，可以证明，最后产生的图形一定是一棵树，所以，只要最后找出这个公司的超级大BOSS，并且找出他来和不来两个状态快乐值最大的那个，这个题就AC啦P.S.:简直累人82开数组dp60002，dpi0代表i号职员不状压dpTSP问题旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是

47、数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。这个有点难懂额没关系，codevs上就有这个题！83状压dpTSP问题旅行商问题，即TSP问题（Travel题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城

48、市的直接通路的时间。输入描述 Input Description第一行一个正整数n （1=n=15）接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同，也就是说道路都是单向的。输出描述 Output Description一个正整数表示最少花费的时间8484样例输入 Sample Input30 1 10 101 0 1 210 1 0 1010 2 10 0样例输出 Sample Output8数据范围及提示 Data Size & Hint1=n=1585样例输入 Sampl