> #include<stdio.h>
> int a[5000],d[5000];
> main()
> {long i,n,len=0;
>  long mid,left,right;
>  scanf("%ld",&n);
>  for(i=0;i<n;i++)
>   scanf("%d",&a[i]);
>  for(i=0;i<n;i++)
>   {
>    if(a[i]>d[len])
>      d[++len]=a[i];
>    else {
> 	 left=1;
> 	 right=len;
> 	  while(left<right-1)
> 	 {
> 	  mid=(left+right)/2;
> 	  if(a[i]>d[mid])
> 	    left=mid+1;
> 	  if(a[i]<d[mid])
> 	    right=mid-1;
> 	  if(a[i]==d[mid])
> 	    break;
> 	 }
> 	  if(a[i]<d[left])d[left]=a[i];
> 	  else if(a[i]<d[right])d[right]=a[i];
>         }
>    }
>   printf("%d",len);
> }

• Re:DP+二分查找,错哪了? (7) ccnujing 2008-05-06 09:39:05