记录编号	200567	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	VacaTionGOD	是否通过	通过
代码语言	Pascal	运行时间	0.008 s
提交时间	2015-10-28 22:32:13	内存使用	0.32 MiB

var
  a,b,c:array[0..10000] of longint;
  L:array[0..10000] of longint;
  i,j,k,n,sum,max:longint;
procedure init;
begin
  n:=0;
  while not eoln do
   begin
     inc(n);
     read(a[n]);
     b[n]:=1; c[n]:=0;
   end;
end;
procedure dp;
begin
  for i:=n-1 downto 1 do  {枚举每一个阶段的状态，设导弹i被拦截}
   begin
     max:=0; j:=0;
     for k:=i+1 to n do  {枚举决策，计算最佳方案中拦截的下一枚导弹}
      if (a[k]<=a[i])and(b[k]>max) then begin max:=b[k]; j:=k; end;
      b[i]:=max+1; //c[i]:=j;    {若导弹i之后拦截导弹j为最佳方案，则记下}
   end;
   max:=0;
   for i:=1 to n do    {枚举求出一套系统能拦截的最多导数}
    if b[i]>max then begin max:=b[i]; j:=i; end;
   writeln(b[j]);
   {while j>0 do
    begin
      write(a[j],' '); j:=c[j];
    end;  }
end;
function add:longint;
begin
  sum:=0;
  L[0]:=maxlongint;
  for i:=1 to n do
  begin
    k:=0;
    for j:=1 to sum do
     if (L[j]>=a[i]) and (L[j]<L[k]) then k:=j;
    if k=0 then
     begin
       sum:=sum+1;
       L[sum]:=a[i];
     end else
     L[k]:=a[i];
  end;
  add:=sum;
end;
begin
assign(input,'missile.in');
reset(input);
assign(output,'missile.out');
rewrite(output);
  init;  {初始化，读入数据}
  dp;
  writeln(add);
close(input);
close(output);
end.
{按照题意，被一套系统拦截的所有导弹中，最后一枚导弹的高度最低。设：k为当前配备的系统数；L[k]为被第k套系统拦截的最后一枚导弹的高度，简称系统k的最低高度（1≤k≤n）。我们首先设导弹1被系统1所拦截（k←1,L[k]←导弹1的高度）。然后依次分析导弹2，……，导弹n的高
若导弹I的高度高于所有系统的最低高度，则断定导弹I不能被这些系统所拦截，应增设一套系统来拦截导弹I(k←k+1,L[k]←导弹i的高度)；若导弹I低于某些系统的最低高度，那么导弹I均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数最少，我们不妨采用贪心策略，选
依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。
}