动态规划初步.ppt

动态规划初步
JSOI2007夏令营B层次(泰州)
常州市第一中学林厚从
问题:城市交通
有n个城市,编号1~n,有些城市之间有路相连,有些则没有,有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市,问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少?
输入格式:
先输入一个n,表示城市数,n<100。
下面的n行,是一个n*n的邻接矩阵map[1..n,1..n]。
map[i,j]=0,表示城市i和城市j之间没有路相连,否则为两者之间的距离。
输出格式:
一个数,表示从城市1走到城市n的最短距离。
输入数据保证可以从城市1走到城市n。
动态规划的引入
常州市第一中学林厚从
输入样例:
11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 6 3 0 0 0 0 0
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 0 0 0
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0
动态规划的引入
常州市第一中学林厚从
设一个数组dis[1..n],dis[i]表示城市1到城市i的最短距离。题目就是要求dis[n]。
根据题目的限制条件:只能从编号小的城市到编号大的城市。显然,我们可以从城市1、城市2、……、城市n-1到城市n,前提是城市i与城市n之间有路,其中i=1,2,3,……,n-1。
所以,dis[n]就应该取dis[i]+map[i,n]中的最小值,且要求map[i,n]<>0,i=1,2,3,……,n-1。
也就是说要求dis[n],就必须先求出dis[1]~dis[n-1],类似于递推算法中的“倒推法”,那么如何求dis[n-1]呢?
dis[n-1] = min{ dis[i] + map[i,n-1] }
且要求map[i,n-1]<>0,i<n-1。
城市交通分析
常州市第一中学林厚从
现在我们把问题一般化,如何求dis[i]呢?其中,i=1..n。
Dis[i] = min { dis[j] + map[j,i]}
要满足:map[j,i]<>0,j=1..i-1
这是一个类似于递归的公式,意思为:要求dis[n]就要先求dis[n-1]~ dis[1],要求dis[n-1]就要先求dis[n-2]~ dis[1],而要求dis[i],就要先求dis[i-1]~ dis[1],……,而dis[1]=0。在具体计算的时候,只要从dis[1]开始“顺推”下去,依次求出dis[2]、 dis[3]、……、 dis[n-1] 、dis[n]即可。
城市交通分析
常州市第一中学林厚从
……
dis[1]:=0;
for i:=2 to n do
begin
min:=maxint; {用打擂台的方法求出最小值}
for j:=1 to i-1 do
if map[j,i]<>0 then
if dis[j]+map[j,i]<min then min:=dis[j]+map[j,i];
dis[i]:=min;
end;
writeln('min=',dis[n]);
城市交通分析
常州市第一中学林厚从
动态规划简介
拦截导弹(NOIP1999)
问题描述:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹的枚数和导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,每个数据之间有一个空格),计算这套系统最多能拦截多少导弹?如果要拦截所有导弹最少要配备多少套这种导弹拦截系统?
样例输入:
8
389 207 155 300 299 170 158 65
样例输出:
6(最多能拦截的导弹数)
2(要拦截所有导弹最少要配备的系统数)
常州市第一中学林厚从
“拦截导弹”问题分析
先讨论第一问:假设a[i]表示拦截的最后一枚导弹是第i枚时,系统能拦得的最大导弹数。例如,样例中的a[5]=3,表示:如果系统拦截的最后一枚导弹是高度为299的话,最多可以拦截第1枚(389)、第4枚(300)、第5枚(299)三枚导弹。
显然,a[1]~a[8]中的最大值就是第一问的答案。关键