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

《NOIP普及讲座4-动态规划2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划2点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题1】装箱问题（noiopenjudge8785）问题描述：有一个箱子容量为V（正整数，0<=v<=20000），同时有n个物品（0

2、例题讲解样例输入2468312797样例输出0。点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i,j]代表前i个物体装在j重的包里的最优解方程：f[i,j]=max(f[i-1,j],f[i-1,j-a[i]);点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题2】宝石手镯（usaco）问题描述：贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自然地，她想从她收集的N(1<=N<=3,402)块宝石中选出最好的那些镶在手镯上。对于第

3、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行每行

4、两个整数，分别表示宝石重量和魅力值。【输出格式】输出只包括一行，这一行只包含一个整数，表示魅力值最多能增加多少。【样例输入】3707110069112【样例输出】3点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i,j]代表前i个宝石戴在j重的手上获得的最大魅力值方程：f[i,j]=max(f[i-1,j],f[i-1,j-a[i])+b[i];点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题3】奶牛打工问题描述：奶牛Bassi

5、e去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬币面值为a[i]。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300)求一共有多少种解决方案？点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行为硬币总值total和硬币种类数n。以下n行为数值a[i]，i=1,2,3...n【输出格式

6、】一行，解决方案数【样例输入】83550251051【样例输出】159点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解0x500x250x100x583x10x500x250x101x578x10x500x250x102x573x10x500x250x103x568x10x500x250x104x563x10x500x250x105x558x10x500x250x106x553x10x500x250x107x548x10x500x250x108x543x10x500x250x109x538x10x500x250x1010x53

7、3x10x500x250x1011x528x10x500x250x1012x523x10x500x250x1013x518x10x500x250x1014x513x1【样例说明】点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i]代表面值为i的钱的换钱方案数方程：f[i]=sum(f[i-a[k]])1<=k<=n;点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题4】滑雪问题描述：Michael喜欢滑雪。这并不奇怪，因为滑雪的确

8、很刺激。可是为了获得速度，滑的区域必需向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表