POJ 1836(双向LIS)

内容目录

双向LIS……居然数组又开小了……

Program P1836;
var
   n,i,j,ans:longint;
   a:array[1..1000] of double;
   ll,lr:array[1..1000] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
begin
   fillchar(ll,sizeof(ll),0);
   fillchar(lr,sizeof(lr),0);

   read(n);
   for i:=1 to n do read(a[i]);
   ll[1]:=1;
   for i:=2 to n do
   begin
      for j:=1 to i-1 do
         if a[j]<a[i] then if (ll[j]>=ll[i]) then
            ll[i]:=ll[j]+1;
      if ll[i]=0 then inc(ll[i]);
   end;
   lr[n]:=1;
   for i:=n-1 downto 1 do
   begin
      for j:=i+1 to n do
         if a[j]<a[i] then if (lr[j]>=lr[i]) then
            lr[i]:=lr[j]+1;
      if lr[i]=0 then inc(lr[i]);
   end;
   ans:=n;
   for i:=1 to n do
      ans:=min(ans,n-(ll[i]+lr[i]-1));
   for i:=1 to n do
      for j:=i+1 to n do
         ans:=min(ans,n-(ll[i]+lr[j]));
   writeln(ans);
end.