动态规划二.ppt

文档介绍：回顾一:数字三角形问题

设有一个三角形的数塔,顶点结点称为根结点,每个结点有一个整数数值。从顶点出发,可以向左走,也可以向右走。如图10一1所示。
问题:当三角形数塔给出之后,找出一条从第一层到达底层的路径,使路径的值最大。
步骤1
二维数组 D(X,y)描述问题,D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。
步骤2:状态转移方程
阶段分析:D(1,1)=13
到第x层的第y个位置有两种可能,要么走右分支得到,要么走左分支得到。
D(X,y)=max{D(X-1,y),D(X-1,y-1}+a(X,y)
D(1,1)=a(1,1)
program sjx;
var
n,j,i:integer;
a:array[0..100,0..100]of integer;
begin
read(n);
for i:=1 to n do
for j:=1 to i do
read(a[i,j]);
for i:=n-1 downto 1 do
for j:=1 to i do
if a[i+1,j]>=a[i+1,j+1]
then a[i,j]:=a[i+1,j]+a[i,j]
else a[i,j]:=a[i+1,j+1]+a[i,j];
writeln(a[1,1]);
end.
回顾二: 拦截导弹(vijos1303)
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹
样例:
INPUT
389 207 155 300 299 170 158 65
OUTPUT
6(最多能拦截的导弹数)
步骤1:用F(i)表示第i项到第一项最长下降序列的长度的值;
步骤2:状态转移方程;
F(i)= 1 i=1
max{F(j)+1}(j<i, bj>bi)
分析:本题实为最长不降序列的一个变种,就是求最长下降序列。那么问题又变得简单了。
步骤3:从前往后的方法来计算最优解
1
2
3
3
3
4
5
6
步骤4:在数组中分析构造出问题的解;
f[1]:=1;len:=1; {求解最大不下降序列长度}
for i:=2 to n do begin
f[i]:=1;
for j:=1 to i-1 do
if (b[i]<b[j])and(f[i]<f[j]+1) then
f[i]:=f[j]+1;
if f[i]>len then len:=f[i] {记录最大值}
end;
INPUT
389 207 155 300 299 170 158 65
也有同学从后往前找最长升序列
program daodan;
var
f,a:array[1..100]of integer;
n,i,j:integer;
begin
read(n);
for i:=1 to n do
read(a[i]);
f[1]:=1;
for i:=2 to n do
begin
f[i]:=1;
for j:=1 to i-1 do
if (a[j]>a[i])and(f[j]+1>f[i])
then f[i]:=f[i]+1;
end;
j:=0;
for i:=1 to n do
if f[i]>j then j:=f[i];
writeln(j);
end.
program daodan;
var
a:array[1..100] of integer;
i,j,k,n:integer;
b:array[0..100] of integer;
begin
read(n);
for i:=1 to n do
read(a[i]);
b[0]:=0; b[n]:=1;
for i:=n-1 downto 1 do
begin
for j:=i+1 to n do
if (a[i]>=a[j]) and (b[j]>k) then k:=b[j];
b[i]:=k+1;
k:=0;
end;
k:=b[1];
for i:=1 to n do
if b[i]>k then k:=b[i];
write(k);
end.
动态规划(二)
经典问题
复赛题型
例一、最短路径问题
求A到G的最短路径。
A
B
C
D
E
F
G
6
4
5