noip1999拦截导弹第二问

答案:2 悬赏:70 手机版

解决时间 2021-04-27 03:35

提问者网友：自食苦果
2021-04-26 07:27

noip1999拦截导弹第二问

最佳答案

五星知识达人网友：詩光轨車
2021-04-26 08:41

以导弹依次飞来的顺序为阶段，设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。

　　状态转移方程：

　　opt[i]=max(opt[j])+1 (h[i]>=h[j],0=
　　最大的opt[i]就是最终的解。

　　这只解决了第一问，对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉，在求一次opt[i]直到打完所有的导弹，但这样做就错了。

　　不难举出反例： 6 1 7 3 2

　　错解： 6 3 2/1/7 正解：6 1/7 3 2

　　其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。

　　求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。

　　复杂度：时间复杂度为O（N2），空间复杂度为O（N）。

　　【源代码】

　　program missile;
　　var
　　i,n,j,ans,min:longint;
　　a,f,s:array[0..100000]of longint;
　　begin
　　n:=0; ans:=0; min:=0;
　　while not(eoln) do
　　begin
　　inc(n);
　　read(a[n]);
　　f[n]:=1; s[n]:=1;
　　end; readln;
　　a[0]:=-maxlongint;
　　for i:=1 to n do
　　begin
　　for j:=i-1 downto 0 do
　　begin
　　if (a[i]>a[j])and(f[j]+1>f[i]) then
　　f[i]:=f[j]+1;
　　if f[i]>ans then ans:=f[i]
　　end;
　　end;
　　a[0]:=maxlongint;
　　for i:=1 to n do
　　begin
　　for j:=i-1 downto 0 do
　　begin
　　if (a[i]s[i]) then
　　s[i]:=s[j]+1;
　　if s[i]>min then min:=s[i];
　　end;
　　end;
　　writeln(min);
　　writeln(ans);
　　end.

全部回答

1楼网友：上分大魔王
2021-04-26 09:02

x1,x2,x3,x4,x5
第二问要用线性动规的最长上升子序列
原因：
若x1我们必须找到换系统最多的一种（保证拦截到每一颗导弹）
即最长上升子序列，每一次上升都必须换一次系统
如最长上升子序列为x2，x4，x5
则，x1>x2(不须换）
x2>x3(不须换）
x3 x4

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！