求最长上升子序列,开始的时候题目完全理解错了,后来被指导才弄明白,两种方法的代码都实现了下,放在下面用于记忆。
动态规划
复杂度o(n*n)
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
| int main() { int num; int t; int s[100000]; int dp[100000]; scanf("%d",&num); while(num--) { scanf("%d",&t); memset(s,0,sizeof(s)); memset(dp,0,sizeof(dp)); for(int i=0;i<t;i++) scanf("%d",&s[i]); for(int i=0;i<t;i++) { int Max = 0; for(int j=0;j<i;j++) { if(s[i]>s[j]) { Max = max(dp[j],Max); } } dp[i] = Max+1; } for(int i = 0;i<t-1;i++) printf("%d ",dp[i]); printf("%d\n",dp[t-1]); } return 0; }
|
方法2
复杂度o(n*lgn)
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 46 47 48 49 50 51 52 53
| #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int num; int t; int s[100000]; int dp[100000]; int stack[100000]; scanf("%d",&num); while(num--) { scanf("%d",&t); memset(s,0,sizeof(s)); for(int i=0;i<t;i++) scanf("%d",&s[i]); memset(dp,0,sizeof(dp)); memset(stack,0,sizeof(stack)); dp[0]=1; stack[0] = s[0]; int top = 0; for(int i =1;i<t;i++) { if(s[i]>stack[top]) { top++; stack[top] = s[i]; dp[i] = top+1; } else{ int low =0,high = top; int mid; while(low<=high) { mid = (low+high)/2; if(s[i]>stack[mid]) low = mid+1; else high = mid-1; } stack[low] = s[i]; dp[i] = low+1; } } for(int i = 0;i<t-1;i++) printf("%d ",dp[i]); printf("%d\n",dp[t-1]); } return 0; }
|