最长公共上升子序列：O(n*m)的算法；
1 #include<cstdio> 2 #include<cstring> 3 #define maxn 1000 4 using namespace std; 5 int a[maxn],b[maxn],f[maxn]; 6 int main() 7 { 8 int t,n,m; 9 scanf("%d",&t); 10 while(t--) 11 { 12 memset(f,0,sizeof f); 13 int ans=0; 14 scanf("%d",&n); 15 for(int i=0;i<n;i++) 16 scanf("%d",&a[i]); 17 scanf("%d",&m); 18 for(int i=0;i<m;i++) 19 scanf("%d",&b[i]); 20 for(int i=0;i<n;i++) 21 { 22 int k=0; 23 for(int j=0;j<m;j++) 24 { 25 if(a[i]==b[j]) 26 if(f[j]<f[k]+1) 27 f[j]=f[k]+1; 28 if(a[i]>b[j]) 29 if(f[k]<f[j]) 30 k=j; 31 } 32 } 33 for(int i=0;i<m;i++) 34 if(ans<f[i])ans=f[i]; 35 printf("%d ",ans); 36 if(t!=0)printf(" "); 37 } 38 return 0; 39 }