NOIP普及讲座4-动态规划2

动态规划2,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题1】装箱问题（noi openjudge 8785） 问题描述： 有一个箱子容量为V（正整数，0=v=20000），同时有n个物品（0 n=30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入 第一行是一个整数V，表示箱子容量。 第二行是一个整数n，表示物品数。 接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自体积。 输出 一个整数，表示箱子剩余空间。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,样例输入 24 6 8 3 12 7 9 7 样例输出 0。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【问题分析】 状态： fi,j代表前i个物体装在j重的包里的最优解 方程： fi,j=max(fi-1,j,fi-1,j-ai);,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【程序实现】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题2】宝石手镯（usaco） 问题描述： 贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自然地，她想从她收集的N(1 = N = 3,402)块宝石中选出最好的那些镶在手镯上。对于第i块宝石，它的重量为W_i(1 = W_i = 400)，并且贝茜知道它在镶上手镯后能为自己增加的魅力值D_i(1 = D_i = 100)。由于贝茜只能忍受重量不超过M(1 = M = 12,880)的手镯，她可能无法把所有喜欢的宝石都镶上。于是贝茜找到了你，告诉了你她所有宝石的属性以及她能忍受的重量，希望你能帮她计算一下，按照最合理的方案镶嵌宝石的话，她的魅力值最多能增加多少。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【输入格式】 输入的第一行有两个整数N(1 = N = 3,402)和M(1 = M = 12,880)，接下来的N行每行两个整数，分别表示宝石重量和魅力值。 【输出格式】 输出只包括一行，这一行只包含一个整数，表示魅力值最多能增加多少。 【样例输入】 3 70 71 100 69 1 1 2 【样例输出】 3,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【问题分析】 状态： fi,j代表前i个宝石戴在j重的手上获得的最大魅力值 方程： fi,j=max(fi-1,j,fi-1,j-ai)+bi;,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【程序实现】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题3】奶牛打工 问题描述： 奶牛Bassie去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬币面值为ai 。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1=total=1000,1=n=1000,1=ai=300)求一共有多少种解决方案？,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【输入格式】 第一行为硬币总值total和硬币种类数n。 以下n行为数值ai，i=1,2,3.n 【输出格式】 一行，解决方案数 【样例输入】 83 5 50 25 10 5 1 【样例输出】 159,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,0 x 50 0 x 25 0 x 10 0 x 5 83 x 1 0 x 50 0 x 25 0 x 10 1 x 5 78 x 1 0 x 50 0 x 25 0 x 10 2 x 5 73 x 1 0 x 50 0 x 25 0 x 10 3 x 5 68 x 1 0 x 50 0 x 25 0 x 10 4 x 5 63 x 1 0 x 50 0 x 25 0 x 10 5 x 5 58 x 1 0 x 50 0 x 25 0 x 10 6 x 5 53 x 1 0 x 50 0 x 25 0 x 10 7 x 5 48 x 1 0 x 50 0 x 25 0 x 10 8 x 5 43 x 1 0 x 50 0 x 25 0 x 10 9 x 5 38 x 1 0 x 50 0 x 25 0 x 10 10 x 5 33 x 1 0 x 50 0 x 25 0 x 10 11 x 5 28 x 1 0 x 50 0 x 25 0 x 10 12 x 5 23 x 1 0 x 50 0 x 25 0 x 10 13 x 5 18 x 1 0 x 50 0 x 25 0 x 10 14 x 5 13 x 1,【样例说明】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【问题分析】 状态： fi代表面值为i的钱的换钱方案数 方程： fi=sum(fi-ak)1=k=n;,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【程序实现】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题4】滑雪 问题描述： Michael喜欢滑雪。这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必需向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点不滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的不滑坡为2417161（从24开始，在1结束）。当然252423321更长。事实上，这是最长的一条。 【输入格式】 第1行为表示区域的二维数组的行数R和列数C(1R，C100)。下面是R行，每行有C个数，代表高度。 【输出格式】 区域中最长滑坡的长度,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【样例输入】 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 【样例输出】 25,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【问题分析】 一个类似最长下降序列，穷举每个最低点。用记忆化搜索写比较方便。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【程序实现】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题5】最小代价子母树 问题描述： 有n堆沙子排成一排，每堆沙子有一个数量，例如：13 7 8 16 21 4 18。任意2堆相邻的沙子可以进行合并，将两堆沙子合并为一堆时，两堆沙子数量的和称为合并这两堆沙子的代价。经过不断的归并，最后将这些沙子归为一堆，而全部归并代价的和称为总代价。例如上列数，其中2种归并方案的代价为： 第1种的总代价为 20+24+25+44+69+87 = 267 第2种的总代价为 15+37+22+28+59+87 = 248 由此可见，不同的归并过程得到的总代价是不一样的。 问题：当n个数给出后，找出一种合理的归并方法，使得总代价最小。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【问题分析】 状态： fi,j代表从i堆合并到j堆所