acm中dp问题简单入门讲解.doc

《acm中dp问题简单入门讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM暑期集训报告院系：专业：年级：学号：姓名：日期：西南交通大学目录31目录1第1章动态规划（dp）21.1简介21.2教师内容51.3基本dp——背包问题61.4若干经典dp及常见优化91.5类似题目10参考文献31附录1暑期集训心得体会31第1章动态规划（dp）（标题采用2号黑体居中，下空1行）1.1简介（标题采用四号黑体，正文内容采用小四号字体，1.5倍行距）在解决问题的时候我们经常遇到这种问题：在多种方式的操作下我们如何得到一个最优的方式让我们得到满意的结果。这时候我们大多人的思想就是贪心。不错贪心确实是一个不

2、错的算法，首先他简单容易想到，我们在操作起来也比较容易。现在我推荐几道我们oj上的贪心算法的题：soj1562药品运输soj1585Climbingmountain。为了引入动归算法我先拿药品运输这道题简单说一下贪心算法。示例1：药品运输（题目采用小四号TimesNewRoman字体）Description5.12大地震后，某灾区急需一批药品，现在有N种药品需要运往灾区，而我们的运输能力有限，现在仅有M辆运输车用来运输这批药品，已知不同的药品对灾区具有不同的作用（“作用”用一个整数表示其大小），不同的药品需要的运输力（必

3、要的车辆运载力）不同，而不同的车辆也具有不同的运输力。同时，我们希望不同的药品用不同的车辆来运输（避免发生混淆）。现在请你帮忙设计一方案，来使得运往灾区的药品对灾区的作用最大。31Input第一行包含一个整数T，表示需要处理的测试数据组数。每一组第一行包括两个整数N,M，分别表示药品总数，及车辆总数。接着第二行包含N个整数（pi<=10000），分别表示每种药品的作用。接着第三行包含N个整数，分别表示每种药品必须得运载力(wi<=1000)。接着第四行包含M个整数，表示每辆车的运输力(c<=1000)；（T<=10;N,

4、M<=1000）Output输出包括T行，每行仅一个整数，表示最大的作用值。SampleInput1111037SampleOutput10在该样例中一辆车只能运一种药品，亲爱的acmer你会很容易想到只要让每一辆车运送在它运输力之下的药品中价值最大的那个就行了，但是这样是不是最优解呢？答案是：恭喜你答对了。但是我怎么选择车呢？你肯定很随意就想到我只要从小到大一个个找就ok了。S31oeasy，right？不过是不是我们所有的问题这样都能很随意的解决呢？Now，接下来的题目，你会发现我们的贪心，贪不过去了。。。。。。示例

5、2：硬币问题（soj1787）Description有N种不同面值的硬币，每种硬币都是有限个，给定一个上限钱数W,问用这些硬币可组成不超过W的最大价值．Input输入有多组测试数据。每一组测试数据为如下形式：WNn1D1n2D2...nNDNW和N分别表示上限钱数和有N种不同面值的硬币，n（i）和D（i）表示面值为D（i）的硬币数量为n（i），其中有1<=i<=N.0<=W<=100000,0<=N<=10,0<=n(i)<=1000,1<=D(i)<=1000.Output对于每一组测试数据，输出这些硬币可组成不超过W

6、的最大价值．SampleInput7353412565335031633450030610015017350031010010501010SampleOutput73563000现在我们试一试如果每一次都取满足条件的最大面值的硬币那么得到的答案是不是正确的呢？拿第一组数据为例：73534125653350第一次取350剩下385第二次取350剩下35第三次取5剩下30依次再取5五次。最终我们取到了350*2+5*6=730咦。。。。不对啊？如果350+125*3+5*2=735岂不是更多？可是我们每一次都取最优解啊，为啥

7、结果不是最优的呢？问题出在第一种取法没有考虑到空间的最大利用化。下面我们引入了动态规划，又习惯称之为dp。严格的说，动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。对于我们acmer来说dp是一种思想，一种化繁为简，化大为小的处理问题的方式。上面的硬币的题就属于dp的一种——背包问题。后面我会仔细讲，现在就不多说了。在学习dp的时候我的建议是，学习如何建立状态方程。如何把主要问题化成子问题分布求解直至得到最终结果。如何用dp的思想来解决最优解问题。当然我不反对多做题。但是大家要通过做题来学到一些

8、东西。dp是一种思想，若思想达不到真正遇到一道题你还是没办法解决。31在处理dp的问题中我们一般想到的解决方法就是用空间换取时间，acm一般对time卡的要比memory要严一般tle要比mle多得多。也就是说我们一般不会爆内存，但是时间比较容易超时。因此有时候我们确实需要用空间换取一定的时间。但是真正的dp对于空间