只要是 求 递增递减 子序列什么的 都可以用那个 那个最长公共子序列的 方法 解决 , 不过 有一个需要注意的地方是 模版序列里面不能有 重复的数字 .
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack> 10 #include<string> 11 #include<sstream> 12 #include<map> 13 #include<cctype> 14 using namespace std; 15 bool cmp(int a,int b) 16 { 17 return a>b; 18 } 19 int main() 20 { 21 int t,n,i,j,a[25],b[25],c[25][25]; 22 scanf("%d",&t); 23 while(t--) 24 { 25 scanf("%d",&n); 26 for(j=i=0;i<n;i++) 27 { 28 scanf("%d",&a[i]); 29 int mark=1; 30 for(int q=0;q<j;q++) 31 { 32 if(a[i]==b[q]) 33 { 34 mark=0; 35 break; 36 } 37 } 38 if(mark) 39 { 40 b[j]=a[i]; 41 j++; 42 } 43 } 44 int count1=j; 45 sort(b,b+count1,cmp); 46 memset(c,0,sizeof(c)); 47 for(int i=1;i<=count1;i++) 48 { 49 for(int j=1;j<=n;j++) 50 { 51 if(b[i-1]==a[j-1]) 52 c[i][j]=c[i-1][j-1]+1; 53 else 54 c[i][j]=c[i][j-1]>c[i-1][j]?c[i][j-1]:c[i-1][j]; 55 } 56 } 57 printf("%d ",c[count1][n]); 58 } 59 return 0; 60 }