MY CODE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<stdio.h> //nlogn算法 /*把10000搞成1000了，错了一下午*/ int n,max; int b[10001],a[10001],len[10001]; int bins(int key) { static int l,r,y; l=0;r=n; while (l<=r){ y=(l+r)>>1; if (b[y]>key) r=y-1;else if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便 else return y; } } int main(){ int i,j; scanf("%d\n",&n); for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;} b[0]=0;//这个初始化要比所有元素小 for (i=1;i<=n;i++){ len[i]=bins(a[i]-1)+1; if (len[i]>max) max=len[i]; if (b[len[i]]>a[i]) b[len[i]]=a[i]; } printf("%d",max); return 0; } |