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

1、动态规划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。单击

2、添加文本，单击添加文本，单击添加文本，单击添加文本，解释经典示例，问题分析状态：fi，j表示装在j个重包中的第一个I个对象的最优解方程：fi，j=max(fi-1，j，fi-1，j-ai)；点击添加文本，点击添加文本，点击添加文本，点击添加文本，程序实现，点击添加文本，点击添加文本，点击添加文本，解释经典示例，示例2 usaco问题描述：贝西在珠宝店闲逛时买了一个心爱的手镯。自然，她想从她收集的N(1=N=3，402)颗宝石中挑选出最好的，并将它们镶嵌在手镯上。至于第二颗宝石，它的重量是W_i(1=W_i=400)，贝西知道它的魅力值D_i(1=D_i=100)，它可以在镶嵌手镯后增加自己的魅

3、力。由于贝西只能忍受重量不超过1米(1=12，880米)的手镯，她可能无法镶嵌所有她喜欢的宝石。所以贝西来找你，告诉你她所有宝石的属性和她能承受的重量。我希望你能帮她计算一下，如果按照最合理的方案镶嵌宝石，她的魅力值还能增加多少。单击添加文本，单击添加文本，单击添加文本，单击添加文本，并解释经典示例。输入格式的第一行有两个整数N(1=N=3，402)和M(1=M=12，880)，接下来的N行每行有两个整数分别代表宝石的重量和魅力值。输出格式输出只包含一行，其中只包含一个整数，表示魅力值最多可以增加多少。示例输入 3 70 71 100 69 1 1 2示例输出3，单击添加文本，单击添加文本，单

4、击添加文本，解释经典示例，问题分析状态：fi，j代表佩戴j重手上的第一个I宝石获得的最大魅力值：fi，j=max (fi-1，j单击添加文本，单击添加文本，单击添加文本，单击添加文本，单击添加文本，程序实现，单击添加文本，单击添加文本，单击添加文本，单击添加文本，单击添加文本，单击添加文本，解释经典示例， 例3奶牛工作问题描述：奶牛Bassie去DQ工作，遇到一位顾客，他给了一大笔钱，所以Bassie不得不面对，以便给顾客零钱。因为奶牛的手指有限，他只能向你求助。 (众所周知，零的总数是总数)(1=总数=1000，1=N=1000，1=人工智能=300)有多少个解？单击添加文本，单击添加文本，

5、单击添加文本，单击添加文本，解释经典示例，输入格式的第一行是硬币总值和硬币类型数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 6

6、3 x 1 0 x 50 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 x 25 0 x 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

7、5 18 X 1 0 X 50 X 25 0 X 10 14 X 5 13 X 1，示例说明，单击添加文本，单击添加文本，单击添加文本，解释经典示例， 问题分析状态：fi表示面值为I: fi=sum (fi-AK) 1的货币兑换方案的数量，单击添加文本，单击添加文本，单击添加文本，单击添加文本，程序实现，单击添加文本，单击添加文本，单击添加文本，解释经典示例，示例4滑雪问题描述：迈克尔喜欢滑雪。 这并不奇怪，因为滑雪真的很刺激。然而，为了获得速度，滑行区域必须向下倾斜，当你滑到斜坡底部时，你必须再次上坡或等待电梯来接你。迈克尔想知道一个地区最长的滑坡。该区域由二维数组给出。数组中的每个数字代表

8、一个点的高度。单击添加文本，单击添加文本，单击添加文本，单击添加文本，解释经典示例，这里有一个示例1 2 3 4 5 16 17 19 6 15 25 20 7 14 23 21 8 13 12 11 10 9一个人不能从某个点滑动到上下左右四个相邻点中的一个，如果且仅当高度降低，在上面的示例中，一个可行的人不能滑动如下。当然，252423321更长。事实上，这是最长的一个。输入格式第一行表示区域的二维阵列的行数r和列数C(1R，C100)。下面是R行，每行有代表高度的C数。输出格式该区域中最长滑坡的长度，单击添加文本，单击添加文本，单击添加文本，解释经典示例，示例输入5 5 123 4 5

9、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。任何两个相邻的沙堆都可以合并。当两堆沙子合并成一堆时，两堆沙子的总和被称为合并两堆沙子的成本。经过连续的合并，这些沙子最终被组合成一堆，所有合并成本的总和称为总成本。例如，在上表中，两个合并方案的成本为：第一个方案的总成本为20.24.25.44.69.87=267，第二个方案的总成本为15.37.22.28.59.87=248。因此，不同合并过程的总成本是不同的。问题：当给定n的个数时，找到一个合理的合并方法来最小化总成本。，单击添加文本，单击添加文本，单击添加文本，单击添加文本，解释经典示例和问题分析状态：fi，j表示