【题解】Greatest Common Increasing Subsequence

vj

唉，把自己当做DP入门选手来总结这道题吧，我DP实在太差了

首先是设置状态的技巧，设置状态主要就是要补充不漏并且适合转移。

这样的区间对区间有个设置状态的技巧：一维钦定一维区间

具体来说，是这个意思：

• 我们要方便记录状态 ，所以我们记录一维区间的答案
• 我们要可以转移，所以我们钦定一个状态方便转移
• 我们要方案互斥，所以我们钦定一个状态方便转移(方法同上，钦定这个技巧同时满足了两种要求)

接下来是对于方案的记录：

• 方案随着DP转移，到时候\(O(n)\)回答

对于这一道题目我们这样设计

设\(dp(i,j)\)表示考虑了\(a_1 \to a_i\)的串，钦定以\(b_j\)串结尾的最长公共上升子序列的最大值

有转移方程

记录方案跟着\(dp\)记录即可，很简单。

才怪！

很难(对于我这样的菜鸡来说)

记录的关键是记录\(B\)串，注意一下实现的顺序。

//@winlere

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57)ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=505;

int A[maxn],B[maxn],last[maxn][maxn],dp[maxn][maxn],stk[maxn];

int main(){

      register int T=qr();

      while(T--){

	    memset(last,-1,sizeof last);

	    memset(dp,0,sizeof dp);

	    memset(stk,0,sizeof(stk));

	    register int n,m,ans=0;

	    n=qr();

	    for(register int t=1;t<=n;++t)

		  A[t]=qr();

	    m=qr();

	    for(register int t=1;t<=m;++t)

		  B[t]=qr();

	    A[0]=B[0]=1<<31;

	    for(register int t=0;t<=n;++t)

		  dp[t][0]=0;

	    for(register int t=1,fr=0;t<=n;++t){

		  dp[0][fr=0]=0;

		  for(register int i=1;i<=m;++i){

			dp[t][i]=dp[t-1][i];

			if(A[t]==B[i]){

			      if(dp[t][i]<dp[t-1][fr]+1)

				    dp[t][i]=dp[t-1][fr]+1,last[t][i]=fr;

			      //cout<<dp[t][i]<<' '<<t<<' '<<i<<' '<<fr<<' '<<last[t][i]<<endl;

			}

			if(B[i]<A[t])if(dp[t-1][fr]<dp[t-1][i])fr=i;

		  }

	    }

	    for(register int t=1;t<=m;++t)

		  if(dp[n][ans]<dp[n][t])

			ans=t;

	    printf("%d\n",dp[n][ans]);

	    //      continue;

	    if(dp[n][ans]<=0) continue;

	    int tmp_i=ans;

	    for(int i=n;i>=1;--i)if(last[i][tmp_i]!=-1)stk[++stk[0]]=A[i],tmp_i=last[i][tmp_i];

	    for(register int t=stk[0];t>=2;--t)

		  printf("%d ",stk[t]);

	    printf("%d \n",stk[1]);

      }

      return 0;

}