内容目录
双向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.