动态规划入门-系列解题报告.doc

动态规划入门动态规划入门 系列解题报告系列解题报告 作者 周娟 时间 2010 5 30 例题例题 组题讲解 安晓冲 1001 City Game hdu1505 矩阵中的最大子段和问题 1006 Dining Cows 1009 Bookshelf2 1010 Charm Bracelet Pku 3624 01背包 1 1002 Exact Change 2 1003 Rhyme Schemes 3 1004 CowRoller Coaster 4 1005 Corn Fields 5 1007 Anniversary party 6 1008 Cow Exhibition hdu 1231 最大连续子序列 最大子段和问题 Hdu 1003 Max Sum 最大子段和问题 Hdu 1081 To The Max 矩阵中的最大子段和问题 7 Pku 1384 Piggy Bank 8 Pku 2626 CHESS 9 Pku 2559 Largest Rectangle in a Histogram 10 Pku 2796 Feel Good http 162 105 81 212 JudgeOnline problem id 1384 Piggy Bank http 162 105 81 212 JudgeOnline problem id 2626 CHESS 以上绿色的 在本文中给出了较完整的解题报告 部分由程道雷同学提供 在今天的动态规划 专题讲座中 安晓冲同学组题的10道 在 hdu 上的 DIY 上 并对它们进行了较详细的讲解 作业要求作业要求 以上黑色的尚未给出解题报告 我在其左边给出了编号 n 假如你的学号是 m 那么满足条件 m 3 n 3的题号 nx 你需要写出这些题目的解题报告来 可以像本文这样即有 word 又有 ppt 这样每个人写3到4个 时间两周之内 令 d n 3 写完好统一交给下面的指定同学 d 收集者 0 程道雷 1 袁传顺 2 彭建欢 由收集者整理 并综合的写出该题优秀的解题报告 当然 除了要完成较完整解题报告的 这里列出的所有黑色和绿色的题目 你们都需要练习并 掌握 本文最后给出 了 各类型 动态规划 练习题的 题号 大家也可以从网上获取 目录 P01 01 背包问题背包问题 3 题目 3 基本思路 3 优化空间复杂度 3 初始化的细节问题 4 一个常数优化 5 小结 5 PKU 3624 CHARM BRACELET 5 背包问题九讲背包问题九讲 8 HDU 1231 最大连续子序列最大连续子序列 10 HDU 1003 MAX SUM 12 HDU 1081 TO THE MAX 17 DIY 1001 CITY GAME 18 DIY 1006 DINING COWS 21 DIY 1009 BOOKSHELF 2 23 PKU 2559 LARGEST RECTANGLE IN A HISTOGRAM 26 各类型各类型 动态规划动态规划 练习题练习题 27 P01 P01 0101 背包问题背包问题 题目题目 有 N 件物品和一个容量为 V 的背包 第 i 件物品的费用是 c i 价值是 w i 求解将 哪些物品装入背包可使价值总和最大 基本思路基本思路 这是最基础的背包问题 特点是 每种物品仅有一件 可以选择放或不放 用子问题定义状态 即 f i v 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的 最大价值 则其状态转移方程便是 f i v max f i 1 v f i 1 v c i w i 这个方程非常重要 基本上所有跟背包相关的问题的方程都是由它衍生出来的 所以有 必要将它详细解释一下 将前 i 件物品放入容量为 v 的背包中 这个子问题 若只考 虑第 i 件物品的策略 放或不放 那么就可以转化为一个只牵扯前 i 1 件物品的问题 如果不放第 i 件物品 那么问题就转化为 前 i 1 件物品放入容量为 v 的背包中 价 值为 f i 1 v 如果放第 i 件物品 那么问题就转化为 前 i 1 件物品放入剩下的容 量为 v c i 的背包中 此时能获得的最大价值就是 f i 1 v c i 再加上通过放入 第 i 件物品获得的价值 w i 优化空间复杂度优化空间复杂度 以上方法的时间和空间复杂度均为 O VN 其中时间复杂度应该已经不能再优化了 但 空间复杂度却可以优化到 O 先考虑上面讲的基本思路如何实现 肯定是有一个主循环 i 1 N 每次算出来二维数组 f i 0 V 的所有值 那么 如果只用一个数组 f 0 V 能不能保证第 i 次循环结束 后 f v 中表示的就是我们定义的状态 f i v 呢 f i v 是由 f i 1 v 和 f i 1 v c i 两个子问题递推而来 能否保证在推 f i v 时 也即在第 i 次主循环中推 f v 时 能够得到 f i 1 v 和 f i 1 v c i 的值呢 事实上 这要求在每次主循环中我 们以 v V 0 的顺序推 f v 这样才能保证推 f v 时 f v c i 保存的是状态 f i 1 v c i 的值 伪代码如下 for i 1 N for v V 0 f v max f v f v c i w i 其中的 f v max f v f v c i 一句恰就相当于我们的转移方程 f i v max f i 1 v f i 1 v c i 因为现在的 f v c i 就相当于原来的 f i 1 v c i 如果 将 v 的循环顺序从上面的逆序改成顺序的话 那么则成了 f i v 由 f i v c i 推知 与本题意不符 但它却是另一个重要的背包问题 P02 最简捷的解决方案 故学习只用一 维数组解 01 背包问题是十分必要的 事实上 使用一维数组解 01 背包的程序在后面会被多次用到 所以这里抽象出一个处 理一件 01 背包中的物品过程 以后的代码中直接调用不加说明 过程 ZeroOnePack 表示处理一件 01 背包中的物品 两个参数 cost weight 分别表明 这件物品的费用和价值 procedure ZeroOnePack cost weight for v V cost f v max f v f v cost weight 注意这个过程里的处理与前面给出的伪代码有所不同 前面的示例程序写成 v V 0 是 为了在程序中体现每个状态都按照方程求解了 避免不必要的思维复杂度 而这里既然 已经抽象成看作黑箱的过程了 就可以加入优化 费用为 cost 的物品不会影响状态 f 0 cost 1 这是显然的 有了这个过程以后 01 背包问题的伪代码就可以这样写 for i 1 N ZeroOnePack c i w i 初始化的细节问题初始化的细节问题 我们看到的求最优解的背包问题题目中 事实上有两种不太相同的问法 有的题目要求 恰好装满背包 时的最优解 有的题目则并没有要求必须把背包装满 一种区别这两 种问法的实现方法是在初始化的时候有所不同 如果是第一种问法 要求恰好装满背包 那么在初始化时除了 f 0 为 0 其它 f 1 V 均 设为 这样就可以保证最终得到的 f N 是一种恰好装满背包的最优解 如果并没有要求必须把背包装满 而是只希望价格尽量大 初始化时应该将 f 0 V 全 部设为 0 为什么呢 可以这样理解 初始化的 f 数组事实上就是在没有任何物品可以放入背包时 的合法状态 如果要求背包恰好装满 那么此时只有容量为 0 的背包可能被价值为 0 的 nothing 恰好装满 其它容量的背包均没有合法的解 属于未定义的状态 它们的 值就都应该是 了 如果背包并非必须被装满 那么任何容量的背包都有一个合法解 什么都不装 这个解的价值为 0 所以初始时状态的值也就全部为 0 了 这个小技巧完全可以推广到其它类型的背包问题 后面也就不再对进行状态转移之前的 初始化进行讲解 一个常数优化一个常数优化 前面的伪代码中有 for v V 1 可以将这个循环的下限进行改进 由于只需要最后 f v 的值 倒推前一个物品 其实只要知道 f v w n 即可 以此类推 对以第 j 个背包 其实只需要知道到 f v sum w j n 即可 即代码中的 for i 1 N for v V 0 可以改成 for i 1 n bound max V sum w i n c i for v V bound 这对于 V 比较大时是有用的 小结小结 01 背包问题是最基本的背包问题 它包含了背包问题中设计状态 方程的最基本思想 另外 别的类型的背包问题往往也可以转换成 01 背包问题求解 故一定要仔细体会上 面基本思路的得出方法 状态转移方程的意义 以及最后怎样优化的空间复杂度 PkuPku 36243624 CharmCharm BraceletBracelet Time Limit 3000 1000ms Java Other Memory Limit 65535 65536K Java Other Total Submission s 31 Accepted Submission s 7 Font Times New Roman Verdana Georgia Font Size Problem Description Bessie has gone to the mall s jewelry store and spies a charm bracelet Of course she d like to fill it with the best charms possible from the N 1 N 3 402 available charms Each charm i in the supplied list has a weight Wi 1 Wi 400 a desirability factor Di 1 Di 100 and can be used at most once Bessie can only support a charm bracelet whose weight is no more than M 1 M 12 880 Given that weight limit as a constraint and a list of the charms with their weights and desirability rating deduce the maximum possible sum of ratings Input Line 1 Two space separated integers N and M Lines 2 N 1 Line i 1 describes charm i with two space separated integers Wi and Di Output Line 1 A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints 4 6 数据组数 背包体积为6 1 4 第一个数为 体积 第二个为价值 2 6 3 12 2 7 求的是在这个体积下的总价值最大为多少 include include define Max a b a b a b int f 12890 int main int n m i v int weight 3403 value 3403 while scanf d d for i 1 i n i scanf d d for i 1 i weight i v f v Max f v f v weight i value i f v 指的是体积为 v 时能够装的最大价值 f v Max f v f v weight i value i 将没有放第 i 件物品时的价值和放了该物品能到的价值中的较大值 作为该体积下的最大价值 printf d n f m 分析过程 for i 1 i weight i v f v Max f v f v weight i value i 一共有4个物品 总容量6 weight 容量 value 价值 第1个物品 1 4 第2个物品 2 6 第3个物品 3 12 第4个物品 2 7 依次考虑将这4个物品放入背包 第1个物品 f 6 4 f 5 4 f 4 4 f 3 4 f 2 4 f 1 4 第2个物品 f 6 10 f 5 10 f 4 10 f 3 10 f 2 6 第3个物品 f 6 22 f 5 18 f 4 16 f 3 12 第4个物品 f 6 23 f 5 19 f 4 16 f 3 12 f 2 7 比如求第2个物品的 f 6 现在开始放第二个物品 总容量是6 第二个物品容量为2 假如选择放第它 那么总容量减去 第二个占用的2 就还剩下4 f 4 就是这容量为4的背包在之前的最大总价值 前面可以通过放第一 个物品得到其价值是4 即 f 4 4 现在的第二个物品价值是6 于是这个背包里有第一个和第二个这 样两个物品了 其总价值是4 6 10 假如不放第二个物品 那么 f 6 就是前面放第一个物品时求出来的 f 6 4 也就是里面只放第1 个物品 总价值就是4 比较 10 和4 取大的 所以 f 6 现在就等于10了 再来看求第2个物品的 f 2 此时总容量为2 第二个物品容量为2 假如选择放第它 那么总容量减去第二个占用的2 就没 有空间了放别的了 总价值就是第2个物品的价值6 假如不放第2个物品 那么 f 2 就是前面放第一个物品时求出来的 f 2 4 也就是里面只放第1个 物品 总价值就是4 比较 6 和4 取大的 所以 f 3 现在就等于6了 下面的 ppt 文件 是对本例的详细演示过程 相信你们看了以后就会非常清楚了 双击下面的 文件可以播放 动 态 规 划 背包问题 周娟 背包问题九讲背包问题九讲 本文前面的 P01 01背包问题 的原理介绍 摘自 Contact Tianyi 写的 背包问题九讲 如下 双击下面的页面可以看到全文 P P0 01 1 0 01 1 背背包包问问题题 题题目目 有 N 件物品和一个容量为 V 的背包 第 i 件物品的费用是 c i 价值是 w i 求解将哪些物品装入背包可使价值总和最大 基基本本思思路路 这是最基础的背包问题 特点是 每种物品仅有一件 可以选择放或不放 用子问题定义状态 即 f i v 表示前 i 件物品恰放入一个容量为 v 的背包可以 获得的最大价值 则其状态转移方程便是 f i v max f i 1 v f i 1 v c i w i 这个方程非常重要 基本上所有跟背包相关的问题的方程都是由它衍生出来的 所以有必要将它详细解释一下 将前 i 件物品放入容量为 v 的背包中 这个子 问题 若只考虑第 i 件物品的策略 放或不放 那么就可以转化为一个只牵扯 前 i 1 件物品的问题 如果不放第 i 件物品 那么问题就转化为 前 i 1 件物品 放入容量为 v 的背包中 价值为 f i 1 v 如果放第 i 件物品 那么问题就 转化为 前 i 1 件物品放入剩下的容量为 v c i 的背包中 此时能获得的最 大价值就是 f i 1 v c i 再加上通过放入第 i 件物品获得的价值 w i 优优化化空空间间复复杂杂度度 以上方法的时间和空间复杂度均为 O VN 其中时间复杂度应该已经不能再优化 了 但空间复杂度却可以优化到 O 先考虑上面讲的基本思路如何实现 肯定是有一个主循环 i 1 N 每次算出来 二维数组 f i 0 V 的所有值 那么 如果只用一个数组 f 0 V 能不能保证 第 i 次循环结束后 f v 中表示的就是我们定义的状态 f i v 呢 f i v 是由 f i 1 v 和 f i 1 v c i 两个子问题递推而来 能否保证在推 f i v 时 也 即在第i次主循环中推f v 时 能够得到f i 1 v 和f i 1 v c i 的值呢 事实上 这要求在每次主循环中我们以 v V 0 的顺序推 f v 这样才能保证推 f v 时 f v c i 保存的是状态 f i 1 v c i 的值 伪代码如下 for i 1 N for v V 0 f v max f v f v c i w i 其中的 f v max f v f v c i 一句恰就相当于我们的转移方程 f i v max f i 1 v f i 1 v c i 因为现在的 f v c i 就相当于原 来的 f i 1 v c i 如果将 v 的循环顺序从上面的逆序改成顺序的话 那么 hduhdu 12311231 最大连续子序列最大连续子序列 Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 5739 Accepted Submission s 2205 Problem Description 给定 K 个整数的序列 N1 N2 NK 其任意连续子序列可表示为 Ni Ni 1 Nj 其中 1 i j K 最大连续子序列是所有连续子序列中元素和最大的一个 例如给定序列 2 11 4 13 5 2 其最大连续子序列为 11 4 13 最大和 为20 在今年的数据结构考卷中 要求编写程序得到最大和 现在增加一个要求 即还需要输出该 子序列的第一个和最后一个元素 Input 测试输入包含若干测试用例 每个测试用例占2行 第1行给出正整数 K 10000 第2行给出 K 个 整数 中间用空格分隔 当 K 为0时 输入结束 该用例不被处理 Output 对每个测试用例 在1行里输出最大和 最大连续子序列的第一个和最后一个元 素 中间用空格分隔 如果最大连续子序列不唯一 则输出序号 i 和 j 最小的那个 如输入样例的第 2 3组 若所有 K 个元素都是负数 则定义其最大和为0 输出整个序列的首尾元素 Sample Input 6 2 11 4 13 5 2 10 10 1 2 3 4 5 23 3 7 21 6 5 8 3 2 5 0 1 10 3 1 5 2 3 1 0 2 0 Sample Output 20 11 13 10 1 4 10 3 5 10 10 10 0 1 2 0 0 0 include include using namespace std int main int i j sum 10005 a 10005 head 10005 int k g bi b int su while scanf d g 0 for i 1 i a i if a i 0 g 记录下负数的个数 如果全部是负数 如下做 if g k cout 0 a 1 a k endl else sum 1 a 1 sum i 存的是以第 i 项结束的最大子段和 head 1 1 h i 存的是以第 i 项为最后一项的最大子段的第一项的座标 for i 2 i k i head i i 先把每个数当成是自己开始自己结束的序列 sum i a i 它的最大序列和为自己 if sum i sum i 1 a i 如果它自己的值小于以它前一项为尾的序列 的和 时 那么这一项就可以连到以它的前一项为结尾的序列中去了 sum i sum i 1 a i head i head i 1 些时它的第一项就是它此时所在序列的第一项 su 9999 for i 1 isu su sum i bi i cout su a head bi a bi endl return 0 HduHdu 10031003 MaxMax SumSum Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 36454 Accepted Submission s 7838 Problem Description Given a sequence a 1 a 2 a 3 a n your job is to calculate the max sum of a sub sequence For example given 6 1 5 4 7 the max sum in this sequence is 6 1 5 4 14 Input The first line of the input contains an integer T 1 T 20 which means the number of test cases Then T lines follow each line starts with a number N 1 N 100000 then N integers followed all the integers are between 1000 and 1000 Output For each test case you should output two lines The first line is Case means the number of the test case The second line contains three integers the Max Sum in the sequence the start position of the sub sequence the end position of the sub sequence If there are more than one result output the first one Output a blank line between two cases Sample Input 2 5 6 1 5 4 7 7 0 6 1 1 6 7 5 Sample Output Case 1 14 1 4 Case 2 7 1 6 求的是最大子段和 输出和 并输出这个小段的 第一个数和最后一个数的下标 b j max sigma a k k i j 1 i i j 1 j0时 b j b j 1 a j 否则 b j a j 动态式 b j max b j 1 a j a j 1 j n 算法如 Maxsum hdu1231中的代码 if sum i 0 是一样的 include int st end int Maxsum int n int a int i b 1000 sum 1000 题目是说最小数为 1000 所以如果全是一些负数 b 0 sum 0 就算不出负数的情况了 for i 1 i0 b a i else b a i if b sum end i sum b return sum int main int t n i m ans s a 100005 scanf d m 0 while t m if m 1 printf n scanf d for i 1 i 1 i 从后住前加 求出第一个数字的下标 s a i if s ans st i printf Case d n m printf d d d n ans st end return 0 5 4 1 2 3 4 To The Max Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 1752 Accepted Submission s 780 Problem Description Given a two dimensional array of positive and negative integers a sub rectangle is any contiguous sub array of size 1 x 1 or greater located within the whole array The sum of a rectangle is the sum of all the elements in that rectangle In this problem the sub rectangle with the largest sum is referred to as the maximal sub rectangle As an example the maximal sub rectangle of the array 0 2 7 0 9 2 6 2 4 1 4 1 1 8 0 2 is in the lower left corner 9 2 4 1 1 8 and has a sum of 15 Input The input consists of an N x N array of integers The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array This is followed by N 2 integers separated by whitespace spaces and newlines These are the N 2 integers of the array presented in row major order That is all numbers in the first row left to right then all numbers in the second row left to right etc N may be as large as 100 The numbers in the array will be in the range 127 127 Output Output the sum of the maximal sub rectangle Sample Input 4 0 2 7 0 9 2 6 2 4 1 4 1 1 8 0 2 Sample Output 15 这一道题目是求最大子段和的升级版 题目大意是 输入一个矩阵 求出一个子矩阵的各个元素之和 要求它是最大的 思想是 想像通过上下两根线 再用一根竖线一夹 夹出所有可能的矩阵 然后将之压缩成一个序 列 求其中的最大子段和 0 2 7 0 9 2 6 2 4 1 4 1 1 8 0 2 比如 i 1 j 2 两个横线夹住第 1 行到第 2 行 上述变成 b 9 4 13 2 那就是对 b 序列求 最大子段和 所求即是 2 行 x 列的矩阵的各元素的和 0 2 7 0 9 2 6 2 4 1 4 1 1 8 0 2 比如 i 1 j 3 两个横线夹住第 1 行到第 3 行 上述变成 b 5 5 17 3 那就是对 b 序列求 最大子段和 所求即是 3 行 x 列的矩阵的各元素的和 HduHdu 10811081 ToTo TheThe MaxMax include int a 101 101 c 101 b 101 int MAXSUM int n int c int sum 129 d 0 for int i 1 i0 d c i else d c i if d sum sum d 求一串数据的最大子段和 假如输入一组 数据 a c d g e 那么以上求的就是这些数据中的最大子序列了 return sum int MAXSUM2 int n int sum 129 max k j i for i 1 i n i 相当于上面的那根线 for k 1 k n k b k 0 存的是第 i 行和 j 行中的 第 k 列 中所有数据的和 for j i j n j 下面那根线 for k 1 ksum sum max return sum int main int k int i j int g while scanf d i k i for j 1 j k j scanf d 只用调一个数就可以了 printf d n g return 0 DiyDiy 10011001 CityCity GameGame Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 824 Accepted Submission s 294 Problem Description Bob is a strategy game programming specialist In his new city building game the gaming environment is as follows a city is built up by areas in which there are streets trees factories and buildings There is still some space in the area that is unoccupied The strategic task of his game is to win as much rent money from these free spaces To win rent money you must erect buildings that can only be rectangular as long and wide as you can Bob is trying to find a way to build the biggest possible building in each area But he comes across some problems he is not allowed to destroy already existing buildings trees factories and streets in the area he is building in Each area has its width and length The area is divided into a grid of equal square units The rent paid for each unit on which you re building stands is 3 Your task is to help Bob solve this problem The whole city is divided into K areas Each one of the areas is rectangular and has a different grid size with its own length M and width N The existing occupied units are marked with the symbol R The unoccupied units are marked with the symbol F Input The first line of the input contains an integer K determining the number of datasets Next lines contain the area descriptions One description is defined in the following way The first line contains two integers area length M 1000 and width N 1000 separated by a blank space The next M lines contain N symbols that mark the reserved or free grid units separated by a blank space The symbols used are R reserved unit F free unit In the end of each area description there is a separating line Output For each data set in the input print on a separate line on the standard output the integer that represents the profit obtained by erecting the largest building in the area encoded by the data set Sample Input 2 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R R R R R R R R R R R R R R R R R R R R R Sample Output 45 0 分析 本题和前面的 1081 方法类似 1001 City Game Hdu1505 include include using namespace std define M 1000000 int m n char d 1001 1001 int maxsum1 int n int a int sum 0 b 0 for int i 1 i0 b a i else b a i if b sum sum b return sum void maxsum2 int m int n char a 1001 1001 int sum 0 int b new int n 1 for int i 1 i m i for int k 1 k n k b k 0 for int j i j m j for int k 1 ksum sum max printf d sum 3 int main int t i j k int sum while scanf d for i 1 i m i for j 1 j d i j maxsum2 m n d printf n return 0 int main int n int a 40000 b 40000 int i j while cin n memset b 0 sizeof b for i 1 i a i b i 1 for j i 1 j 1 j if a j a i b i max b i b j 1 int maxd b 1 for i 2 i n i if maxd b i maxd b i cout n maxd endl return 0 题意 对一个序列 a 例如 a 2 1 1 1 2 2 1 要使得它成为严格的上升序列 也就是右边 的不能比左边大 那么要改变的最少多少个位置上的数字 这里有一个前提是 每个位置上的数是 1 或 2 如果要改变 那么 1 可以变为 2 2 可以变为 1 分析 先求一个序列 b 记录了 a 中每个元素的 见下面的例子就明白了 i1234567 a2111221 b11234 5 最大 1 结果 1111222 b i 在数据 a i 的左边的连续序列中有几个比 a i 小的 再加上1个自己 此例最大的是 b 6 5 也就是 1 1 1 2 2 这4个数字作为一整块严格上升序列 LIS 可以 不要改变 只需要改变它左边和右边的 a 1 和 a 7 即可 DiyDiy 10091009 BookshelfBookshelf 2 2 Time Limit 3000 1000ms Java Other Memory Limit 65535 65536K Java Other Total Submission s 22 Accepted Submission s 13 Font Times New Roman Verdana Georgia Font Size Problem Description Farmer John recently bought another bookshelf for the cow library but the shelf is getting filled up quite quickly and now the only available space is at the top FJ has N cows 1 N 20 each with some height of Hi 1 Hi 1 000 000 these are very tall cows The bookshelf has a height of B 1 B S where S is the sum of the heights of all cows To reach the top of the bookshelf one or more of the cows can stand on top of each other in a stack so that their total height is the sum of each of their individual heights This total height must be no less than the height of the bookshelf in order for the cows to reach the top Since a taller stack of cows than necessary can be dangerous your job is to find the set of cows that produces a stack of the smallest height possible such that the stack can reach the bookshelf Your program should print the minimal excess height between the optimal stack of cows and the bookshelf Input Line 1 Two space separated integers N and B Lines 2 N 1 Line i 1 contains a single integer Hi Output Line 1 A single integer representing the non negative difference between the total height of the optimal set of cows and the height of the shelf Sample Input 5 16 3 1 3 5 6 Sample Output 1 Author anchong Source 背包 题意 5 16 3 1 3 5 6 5 个 cow 书架高度 16 选其中几个 cow 垒起来 使得其高度超过书架高度 16 但又超过得最少 第 1 种取法 3 3 5 6 17 比 16 高出了 1 第 2 种取法 3 1 3 5 6 18 比 16 高出了 2 选上面第 1 种取法 输出所高出的部分 即输出 1 分析 已知书架高度 h1 16 所有 cow 垒起来的总高度 h3 18 题目要求的是 h2 h1 令 m1 h3 h1 m2 h3 h2 所求 m3 h2 h1 通过 m3 m2 m1 来求 m3 那么我们只要求出 m2 就可以得到结果了 m2 可以看做一个 0 1 背包问题 背包的总容量是 m1 在 n 个 cow 里取若干个放到这个背包里 使得总价值最大 1009 Bookshelf2 include using namespace std int n m int C 25 int f 1000010 int main while scanf d d for int i 1 i n i scanf d sum C i memset f 0 sizeof f m sum m 多了多少 for int i 1 i C i v if f v f v C i C i f v f v C i C i cout f v f v endl cout endl printf d n m f m return 0 PkuPku 25592559 LargestLargest RectangleRectangle inin a a HistogramHistogram Time Limit 1000MSMemory Limit 65536K Total