信息学奥赛中的动态规划

主讲人：FireStorm数字三角形——IOI1994题目描述Description如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。输入描述InputDescription第一行是数塔层数N(1=N=100)。第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。输出描述OutputDescription输出最大值。样例输入SampleInput51311812726614158127132411样例输出SampleOutput86解法1：暴搜DFS一遍遍历整个数字三角形，对于每个节点，我们有2个选择，那么，n层的数字三角形有2^n种可能，所以时间复杂度为O(2^n)TLE！解法2：贪心一路下去只找最大的可以吗？WA!解法3：最长路将整个数字三角形看作一个由点和边组成的图，以a[1][1]为起点，求它到a[n][i](1=i=n)的最长路Dijkstra算法：本题部分数据有负值……SPFA算法：O(kM)的话应该能行Bellman-Ford算法：O(VE)有点危险啊Floyd算法：O(n^3)你确定要用吗？方法可行但是打起来好麻烦……还有什么更好的算法吗？当然有！那就是本课要讲的内容——动态规划分析这个数字三角形，我们可以发现：一个节点只会受到上面两个节点的值的影响，而上面节点的值也只会受到更加上面的节点的值的影响……由此可写出递归式dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]上面这个递归式在动态规划中被叫做状态转移方程式，根据这个式子，我们可以从dp[1][1]开始递推，直到数字三角形的最后一行。时间复杂度O(n^2)，完全无压力~动态规划是优美的动态规划是神奇的动态规划是有趣的动态规划是简单的动态规划是卡骗分的动态规划是禁贪心的动态规划是防止爆0的动态规划最简单最好玩了我最喜欢动态规划了！！！什么鬼！！！0-1背包问题——MerkelandHellman1978——NOIP2005普及组题目描述Description由于该题目的题目描述版本过多，不再描述输入描述InputDescription输入第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表最大重量，M代表物品的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某个物品的时间和每个物品的价值。输出描述OutputDescription输出包括一行，这一行只包含一个整数，表示在不超过规定重量的情况下，可以拿到的最大价值。样例输入SampleInput1111样例输出SampleOutput1数据范围及提示DataSize&Hint【数据规模】对于30%的数据，M=10；对于全部的数据，M=100。老规矩：暴搜TLE贪心一定WA最短路你可以试试……怎么办？动态规划才是王道！我们先分析下暴搜的过程：我们对每个物品进行了搜索，产生了大量的状态，每个状态包括三个要点：1.目前已用的背包的容量，这个不用多说2.目前已经获得的价值，这个也不用多说3.目前已经处理了多少物品，记录下已经处理物品数量的原因是由于每个物品只能拿一个，所以要记录下已经处理了多少物品，防止以后重复处理有什么想法没？为什么不记录下相同的状态时的最优策略呢？在使用相同的容量和处理了相同的物品后，剩下的搜索过程应该是相同的，假如共有n个物品，我们已经处理了m个，那么还需要处理的物品数量就是n-m，但是在背包剩余体积为v的情况下，剩下n-m个物品产生的最优解应该是相同的，这样就可以简化搜索过程，但是前面的怎么办呢？前面的当然要最好的！于是，我们得到一条结论：在其他状态均相同的情况下，选择最好的总是对的！所以，我们可以开始优化这个搜索了：每次搜索到一个状态，就从之前搜到过的状态里找一遍，如果看见可以替换的状态就更新……众：你不觉得更慢了么……所以，怎么办呢？你还记的桶排序吗？直接用数组下标记录，时间复杂度O(1)这个可以这样做吗？没问题！看数据范围：1=T=1000，1=M=100，状态只需要记录下重量和已处理的物品数，空间复杂度O(TM)，128MB内存没问题至于状态转移方程式的话：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+c[i])我一般习惯写成：dp[i+1][j]=max(dp[i][j],dp[i+1][j])dp[i+1][j+v[i]]=max(dp[i+1][j+v[i]],dp[i][j]+c[i])这个看个人喜好就可以了，没有强制要求的处理时，只要for一遍，把数组填充好就可以啦，时间复杂度O(TM)P.S.：这字母是谁规定的，这么恶心如果卡你空间怎么办？滚蛋动数组你还记得斐波那契问题怎么做的吗？c=a+ba=bb=c根本不用开一个数组嘛！这个问题也一样，除了前一行，其他的状态根本就用不到嘛！那么：也就是说，数组只留2行就可以了，每处理完一行，就把第二行的结果放回第一行，继续处理滚动数组是用时间换空间的一种策略有没有更好的方法呢？背包问题可以用一维数组解决你造吗？由于重量没有负数，所以可以直接向后转移，而且不用向下转移了，但这样就有可能重复处理一个物品，怎么办？很简单，改变下方向，从后往前处理就可以啦~至此，01背包完满完成~难度增加的背包问题更加喜(sang)闻(xin)乐(bing)见(kuang)的背包问题超大背包问题每个物品只能拿一次，物品数量M=100，背包容量T=10^9，每个物品的价值=100，每个物品的重量=10^9由于本题物品的价值非常小，所以可以将dp数组改为由已处理的物品数量和价值，数组内存储内容改为当前所需的重量即可二维背包问题对于每个物品，分别有体积v和重量w，求体积和重量均不超标的情况下可以拿到的最大价值维数改为三维，改变下转移，也可简化为二维，从后往前for得出正确答案完全背包问题每个物品可以拿无限次，只要不超过最大重量即可思路1：背包+枚举在状态转移时枚举每个物品可以拿的次数，时间复杂度O(VNK)优化1：减少物品种类对于一个物品来说，假如它的重量大于等于另一个物品且它的价值比另一个物品低，那么要它何用？可以直接省略掉该物品，所以只要先预对所有物品进行一遍O(n^2)的预处理，就能带来很大的优化优化2：转化为0-1背包将一个物品看成多个物品，时间复杂度没有发生变化但是大家记得一个叫做鬼谷子的钱袋的题吗？如一个物品最多可以拿10个，则可以拆分成：1个该物品，2个该物品，3个该物品，4个该物品，达到log(k)的级别，也是个不错的优化思路2：用一维背包解决大家还记得一维的背包解决方案吗？此题也可，只不过为了使一个物品可以重复计算，只需要将从后往前改为从前往后即可，时间复杂度O(VN)多重背包问题对于每个物品，可以拿不同的次数，如：有的1次，有的10次，有的100次……依然采取之前的二进制思想，简化问题混合背包问题对于一个背包问题，有多种物品可以选择：有只能拿一件的，有可以拿多个的，有可以无限拿的，这时候应该怎么办？这个问题综合了三种背包，代表这个问题可以使用各种背包问题的优化方法！优化1采用完全背包问题的优化方式1，即可瞬间去除大量无用物品P.S.:简直就是个垃圾清理器优化2先不考虑多重背包，只考虑01背包和完全背包，那么，就可以用喜闻乐见的一维数组方法求解，只要在转移前判断下是从前往后还是从后往前转移就行了，那么多重背包怎么办？笨！用二进制转成多个01背包啊！金明的预算方案(NOIP2006提高组)主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无题目描述Description金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，右图就是一些主件与附件的例子。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。输入描述InputDescription第1行，为两个正整数，用一个空格隔开：Nm（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q0，表示该物品为附件，q是所属主件的编号）输出描述OutputDescription只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(200000)样例输入SampleInput100058002040051300514003050020样例输出SampleOutput2200数据范围及提示DataSize&Hint无对于每个主件，它最多有2个附件，那么每个物品只有这几种情况：1.不带附件2.带附件A3.带附件B4.带附件A和B5.连主件都不拿那么只要在状态转移时枚举每个物品拿还是不拿，拿几个附件即可……不过好好看看还是能发现些什么的：这题放眼望去应该是个树形dp，好可怕的说……至此，背包问题全部完成！但这仅仅是简单的背包问题而已区间型DP别看我看标题石子归并经典区间型dp题目描述Description有n堆石子排成一列，每堆石子有一个重量w[i],每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。输入描述InputDescription第一行一个整数n（n=100）第二行n个整数w1,w2...wn(wi=100)输出描述OutputDescription一个整数表示最小合并代价样例输入SampleInput44114样例输出SampleOutput18数据范围及提示DataSize&Hint无分析下花费吧花费是由两堆石子组成的，即：cost[i][j]=w[i]+w[i+1]+……+w[j-1]+w[j]要合并i-j堆，必须要先合并i~k堆和k+1~j堆，可以得出递推式js(i,j)=w[i]i=jmin(js(i,i)+js(i+1,j)……js(i,j-1)+js(j,j))+cost[i][j]i≠j然后怎么办？递归处理吗？我说你百分百超时你信吗？这节课学的啥？动态规划啊！开个数组，记录下来，直接转成递推，时间复杂度O(n^2)，完全无压力P.S.:这个题写代码还是稍微有点难度的，所以写不出来的童鞋可以考虑放(mei)弃(tian)本(yi)题(bian)能量项链(noip2006)题目描述Description在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等