动态规划初步.ppt

动态规划初步9280158089动态规划应用举例
例1、挖地雷(NOIP1996 )
在一个地图上有N个地窖(N<=200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的。某人可以从任一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。
[输入]
N {地窖的个数}
W1 W2……WN {每个地窖中的地雷数}
X1 Y1 {表示可从X1到Y1}
X2 Y2
……
0 0 {表示输入结束}
[输出]
K1——K2——……——Kv
{挖地雷的顺序}
MAX {最多挖出的地雷数}
输入:
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
输出:
3-4-5-6
34
[挖地雷问题分析]
设W(i)为第i个地窖所藏有的地雷数,A(i,j)表示第i个地窖与第j个地窖之间是否有通路,F(i)为从第i个地窖开始最多可以挖出的地雷数。
动态规划应用举例
F(i)= MAX { F(j) + W(i) }
(i<j<=n , A(i,j)=1)
边界:F(n)=W(n)
于是就可以通过递推的方法,从后(即F(n))往前逐个找出所有的F(i),再从中找一个最大的即为第2问的解。
对于具体所走的路径(第2问),可以通过一个向后的链接来实现。
动态规划应用举例
例2、接苹果(apples)
农场的夏季是收获的好季节。在John的农场,他们用一种特别的方式来收苹果:Bessie摇苹果树,苹果落下,然后John尽力接到尽可能多的苹果。作为一个有经验的农夫,John将这个过程坐标化。他清楚地知道什么时候(1<=t<=1,000,000)什么位置(用二维坐标表示,-1000<=x,y<=1000)会有苹果落下。他只有提前到达那个位置,才能接到那个位置掉下的苹果。一个单位时间,John能走s(1<=s<=1000)个单位。假设他开始时(t=0)站在(0,0)点,他最多能接到多少个苹果?
输入:第一行是两个整数N(苹果个数,N<=5000)和S(速度);
第2..N+1行:每行3个整数Xi,Yi,Ti,表示每个苹果掉下
的位置和落下的时间。
输出:仅一行,一个数,表示最多能接到几个苹果。
动态规划应用举例
[样例]

5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2

3
说明:John可以接到第1,5,4个苹果。
动态规划应用举例
[接苹果问题分析]
首先划分阶段,很明显,按照苹果掉落的时间先后顺序来划分阶段,所以有必要按时间从小到大给各个苹果排个序,并按顺序标上1..n的编号。
假如John现在正站在某个位置上接苹果,为了使他到当前为止接到的苹果数最大,我们想要知道的是他前一步在哪个位置接苹果,并且要知道到那个位置为止接到的苹果最多是多少。
假设dis(i,j)表示第i个苹果与第j个苹果之间的直线距离。time(i)表示第i个苹果掉落的时刻。F(i)表示John当前站在第i个苹果的位置上最多能接到的苹果总数(包括他以前接的)。
F(i) = max { F(j) + 1 }
其中0<=j<=i-1,且dis(i,j)<=(time(i)-time(j))*S
初始条件:F(0)=0
表示John站在出发点(0,0)时一个苹果也没接到。
动态规划应用举例
例3、低价购买(buylow)
“低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的购买建议:低价购买,再低价购买。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!
你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。
你将被给出一段时间内一支股票每天的出售价(216范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买,再低价购买”的原则。
写一个程序计算最大购买次数。
这里是某支股票的价格清单:
日期 1 2 3 4 5 6 7 8 9 10 11 12
价格 68 69 54 64 68 64 70 67 78 62 98 87
最优秀的投资者可以购买最多4次股票,可行方案中的一种是:
日期 2 5 6 10
价格 69 68 64 62
动态规划应用举例
[输入]
输入共两行,第1行为 N (1 <= N <= 5000),表示股票发行天数;
第2行: N个数,是每天的股票价格。
[输出]
输出两个数:最大购买次数和拥有最大购买次数的方案数(<=231)
当两种方案“看起来一样”时(就是说它们构成的价