作业帮pascal拦截导弹问题的解题思路?某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 06:37:54
pascal拦截导弹问题的解题思路?某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不
pascal拦截导弹问题的解题思路?
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数）,该导弹数量不超过100个,计算这套系统最多能拦截多少导弹,分别是哪些导弹,本题保证所给的数据最优解只有一组输.
注意还有如何输出每个被拦截导弹的高度.
我知道此题是利用不升子序列解决的方法.但是不是很明白,希望能将每一步程序是什么意思都表明一下.
pascal拦截导弹问题的解题思路?某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不
主要思想是动态规划中的求最长不上升序列.
type
fnode=record
shuliang,qianqu:integer;//从开始到当前导弹,能得到的最大长度
end;
var
a,b:array[1..100] of integer;
f:array[1..100] of fnode;
s:ansistring;
p,i,j,n,c,max:integer;
begin
assign(input,'lanjie.in'); reset(input);
assign(output,'lanjie.out'); rewrite(output);
readln(s);//处理输入数据
n:=0;
p:=pos(' ',s);
while p0 do
begin
inc(n);
val(copy(s,1,p-1),a[n],c);
delete(s,1,p);
p:=pos(' ',s);
end;
inc(n);
val(s,a[n],c);
fillchar(f,sizeof(f),0);
f[1].shuliang:=1; f[1].qianqu:=0;//初始化开始第一个导弹
for i:=2 to n do
begin
max:=0;
for j:=1 to i-1 do//枚举之前的导弹
if (a[j]>=a[i])and(f[j].shuliang>max) then//需要符合的条件,比当前导弹高,并且数量最多
begin p:=j; max:=f[j].shuliang; end;
f[i].shuliang:=max+1; f[i].qianqu:=p;//记录下之前最长序列的最后一个元素,也就是当前导弹的前趋
end;
max:=0;
for i:=1 to n do//取得最长的长度
if f[i].shuliang>max then
begin p:=i; max:=f[i].shuliang; end;
writeln(max); i:=0;
while p0 do//根据记录的前趋,得到整个最长序列
begin
inc(i);
b[i]:=p;
p:=f[p].qianqu;
end;
for j:=i downto 2 do
write(a[b[j]],' ');
writeln(a[b[1]]);
close(input); close(output);
end.