搜索
主讲人：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.带附件A3.带附件B4.带附件A和B5.连主件都不拿那么只要在状态转移时枚举每个物品拿还是不拿，拿几个附件即可……不过好好看看还是能发现些什么的：这题放眼望去应该是个树形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颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等