【题目大意】

给定两个序列，求其最长不下降公共子序列

【思路分析】

就是一道裸的模板题？(我居然忘了模板怎么打了QAQ……)

$f[i][j]$表示匹配到$a_i$和$b_j$的最长不下降公共子序列长度，分两种情况：

1.$a_i>b_j$：这种情况不需要转移，但是要记录一下长度，以便后面转移的时候找最大值

2.$a_i=b_j$：这就是配对成功的情况，那么从前面记录的最大值+1转移过来，并且要记录一下取到最大值的位置。

然后因为最后要输出这个公共子序列，所以中间要存一下。

【代码实现】

1 #include
      
        2 #include
       
         3 #include
        
          4 #define go(i,a,b) for(register int i=a;i<=b;i++) 5 #define back(i,a,b) for(register int i=a;i>=b;i--) 6 using namespace std; 7 const int M=503; 8 int n,l1,l2,len; 9 int a[M],b[M];10 int f[M][M],pre[M][M];11 int main(){12     scanf("%d",&n);13     while(n--){14         memset(f,0,sizeof(f));memset(pre,-1,sizeof(pre));15         scanf("%d",&l1);16         go(i,1,l1) scanf("%d",&a[i]);17         scanf("%d",&l2);18         go(i,1,l2) scanf("%d",&b[i]);19         go(i,1,l1){20             int t=0,k=0;21             go(j,1,l2){22                 f[i][j]=f[i-1][j];23                 if(a[i]>b[j]&&t
         
          f[i][j]) f[i][j]=t+1,pre[i][j]=k;25             }26         }27         int t=1;28         go(i,1,l2) if(f[l1][i]>f[l1][t]) t=i;//找到最长公共子序列29         printf("%d\n",f[l1][t]);30         if(!f[l1][t]) continue;31         vector
          
           ans;32         back(i,l1,1)33             if(pre[i][t]!=-1) ans.push_back(a[i]),t=pre[i][t];//记录答案34         printf("%d",ans[ans.size()-1]);35         back(i,ans.size()-2,0) printf(" %d",ans[i]);36         puts("");37     }38     return 0;39 }