ZOJ2432 Greatest Common Increasing Subsequence 题解报告
【题目大意】
给定两个序列，求其最长不下降公共子序列
【思路分析】
就是一道裸的模板题？(我居然忘了模板怎么打了QAQ……)
$f[i][j]$表示匹配到$a_i$和$b_j$的最长不下降公共子序列长度，分两种情况：
1.$a_i>b_j$：这种情况不需要转移，但是要记录一下长度，以便后面转移的时候找最大值
2.$a_i=b_j$：这就是配对成功的情况，那么从前面记录的最大值+1转移过来，并且要记录一下取到最大值的位置。
然后因为最后要输出这个公共子序列，所以中间要存一下。
【代码实现】
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 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-1][j]) t=f[i-1][j],k=j; 24 if(a[i]==b[j]&&t+1>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 ",f[l1][t]); 30 if(!f[l1][t]) continue; 31 vector<int>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 }