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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include<stdio.h> #include<stdlib.h> using namespace std; int q(int *num,int B,int E,int elem) { if(B>=E) return E; int mid = (B+E)/2; if(num[mid]>elem) return q(num,mid+1,E,elem); else return q(num,B,mid,elem); } int cmp(M a,M b) { return a.weight<b.weight; } int main() { int t,num[5005]; int tm,top = 0; int input[5005]; scanf("%d",&t); while(t--) { scanf("%d",&tm); for(int i = 0;i<tm;++i) scanf("%d",&input[i]); top = 0; num[0] = input[0]; ++top; for(int i = 1; i < tm;++i) { if(input[i]<num[top-1]) { num[top++]=input[i]; }else{ num[q(num,0,top-1,input[i])]=input[i]; } } printf("%d\n",top); } return 0; }
|