#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+二分查找,错哪了? (25) xinz 2005-12-16 13:10:10
• 规模为1000，n^2的算法就可以过了，不用二分的 (0) xinz 2005-12-16 13:16:21
  • 那你试试这题http://acm.hnu.cn:8080/online/?action=problem&type=show&id=10027 (539) yiyiyi4321 2005-12-16 13:52:28
    • n^2的我早过拉,假如是50000,铁定超时.所以我想写个N*LOGN的,二分老写不对 (0) yiyiyi4321 2005-12-16 13:54:59
    • 嗯，到你们那试了下，50001规模的 187ms AC了。 哪里还可优化呢？ (5) wrong123 2005-12-16 23:16:27
• 好像二分有问题， 我的是这样： (621) wrong123 2005-12-16 23:13:32
  • 谢拉! (0) yiyiyi4321 2005-12-17 08:43:37
  • 不过你这样做好象还是过不了2533 (0) yiyiyi4321 2005-12-17 09:01:08
    • 这个题好像数据有问题，看Discuss吧 (0) TN 2005-12-17 09:24:07
    • 我知道了,刚刚发现我的程序过不了1 0这组数据:) (0) yiyiyi4321 2005-12-17 09:28:13
      • 加个d[0] = -1 你那个二分也有问题 (310) first 2006-02-23 16:33:17
• Re:DP+二分查找,错哪了? (598) ccnujing 2008-05-06 09:38:44
  • Re:DP+二分查找,错哪了? (7) ccnujing 2008-05-06 09:39:05