#include <stdio.h>
const int L=1001;
float a[L],up[L],down[L];
int f1[L],f2[L],ans,now,n;

int find(float x,int right,float b[]){
     if (x<=b[1])return 1;
	 int i=1,j=right;
	 while(i!=j-1||i==j){
	 	  if (b[right=(i+j)/2]<x)i=right;
		  else j=right; 
		  }
     return j;
     }

int main(void){
    freopen ("1836.in","r",stdin);
    freopen ("1836.out","w",stdout);
    scanf ("%d",&n);
    for (int i=1;i<=n;i++)scanf ("%f",a+i);
    f1[1]=1,up[1]=a[1],now=1;
    for (int i=2;i<=n;i++)
		if (a[i]>up[now])up[++now]=a[i],f1[i]=now;
		else f1[i]=find(a[i],now,up),up[f1[i]]=a[i];
    f2[n]=1,down[1]=a[n],now=1;
    /*for (int i=1;i<=n;i++)
        printf ("%.0f ",up[i]);
    printf ("\n");*/
	for (int i=n-1;i>=1;i--)
		if (a[i]>down[now])down[++now]=a[i],f2[i]=now;
		else f2[i]=find(a[i],now,down),down[f2[i]]=a[i];
	for (int i=1;i<=n;i++)
	    for (int j=i+1;j<=n;j++)
	        if (f1[i]+f2[j]>ans)ans=f1[i]+f2[j];
    printf ("%d",n-ans);
    return 0;
    }

• Re:n log n算法 (16) stupidjohn 2011-03-30 21:52:24