《动态规划初步》.ppt

动态规划初步
JSOI2007夏令营B层次（泰州）
精选ppt
问题：城市交通
有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城起分析和体会其中的方法和过程，然后再独立去思考和实践。
精选ppt
动态规划简介
拦截导弹（NOIP1999）
问题描述：
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？
样例输入：
8
389 207 155 300 299 170 158 65
样例输出：
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）
精选ppt
“拦截导弹”问题分析
先讨论第一问：假设a[i]表示拦截的最后一枚导弹是第i枚时，系统能拦得的最大导弹数。例如，样例中的a[5]=3，表示：如果系统拦截的最后一枚导弹是高度为299的话，最多可以拦截第1枚（389）、第4枚（300）、第5枚（299）三枚导弹。
显然，a[1]~a[8]中的最大值就是第一问的答案。关键是怎样求得a[1]~a[8]？
我们换一个角度，假设现在已经求得a[1]~a[7]（注：在动态规划中，这样的假设往往是很必要的），那么怎样求a[8]呢？
a[8]要求系统拦截的最后1枚导弹必须是65，也就意味着倒数第2枚被拦截的导弹高度必须不小于65，则符合要求的导弹有389、207、155、300、299、170、158。
精选ppt
假如拦截的倒数第2枚导弹是300，则a[8]=a[4]+1；假如拦截的倒数第2枚导弹是299，则a[8]=a[5]+1；类似地，a[8]还可能是a[1]+1、a[2]+1、……。当然，我们现在要求得是以65结尾的最多导弹数目，因此a[8]要取所有可能值的最大值，即：a[8] = max{ a[1]+1，a[2]+1，……，a[7]+1}
= max{a[i]} + 1 (i=1..7)。
类似地，我们可以假设a[1]~a[6]为已知，来求得a[7]。同样，a[6]、a[5]、a[4]、a[3]、a[2]也是类似求法，而a[1]就是1，即如果系统拦截的最后1枚导弹是389，则只能拦截第1枚。
“拦截导弹”问题分析
精选ppt
这样，求解过程可以用下列式子归纳：
a[1]=1
a[i]=max{a[j]} + 1
其中：i>1，j=1..i-1，且h[j]>=h[i]
第一问的答案就是a[1]~a[8]中的最大值。
“拦截导弹”问题分析
精选ppt
longest[1]:=1;
for i:=2 to n do {分阶段求出每步的最优值}
begin
maxlong:=1;
for j:=1 to i-1 do
if h[i]<=h[j] then
if longest[j]+1>maxlong then maxlong:=longest[j]+1;
longest[i]:=maxlong
end;
maxlong:=longest[1]; {以下打擂台求出最大值}
for i:=2 to n do
if longest[i]>maxlong then maxlong:=longest[i];
writeln('max=',maxlong);
这种解题方法就称为“动态规划”
“拦截导弹”问题分析
精选ppt
“拦截导弹”问题分析
关于第二问：
由于它紧接着第一问，所以很容易受前面的影响，多次采用第一问的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7 5 4 1 6 3 2”， 最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结果为3套系统；但其实只要2套，分别击落“7 5 4 1”与“6 3 2”。所以不能用多次“动态规划”的方法做，那么，正确的做法又是什么呢？
我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要，上面错误的