f[i,0]表示前i个，第i个必须在队里，到末尾为降序的最小出队人数。f[i,1]为升序。
直接动规一遍完事。
var
 a:array[0..1000]of real;
 f:array[0..1000,0..1]of longint;
 n,i,j,ans:longint;
function min(x,y:longint):longint;
 begin
  if x<y then exit(x) else exit(y);
 end;
begin
 readln(n);
 for i:=1 to n do read(a[i]);
 fillchar(f,sizeof(f),127);
 for i:=1 to n do
  for j:=0 to i-1 do
   begin
    if (a[j]<a[i])or(j=0) then f[i,1]:=min(f[i,1],f[j,1]+i-j-1);
    if (a[j]>a[i])or(j=0) then f[i,0]:=min(f[i,0],f[j,0]+i-j-1);
    if a[j]>=a[i] then f[i,0]:=min(f[i,0],f[j,1]+i-j-1);
   end;
 ans:=maxlongint;
 for i:=1 to n do
  ans:=min(ans,min(f[i,1],f[i,0])+n-i);
 writeln(ans);
end.

• Re:可以不枚举中点不求LIS，超简短方法，见内： (11) yan_peng 2011-07-30 16:36:23