题目链接

最长公共上升子序列

\(f[i][j]\)表示\(A\)的前\(i\)个数，匹配\(B\)的第\(j\)个数，且\(B[j]\)必选时的最长公共上升子序列长度

转移：

if(A[i]==B[j]) dp[i][j]=max(dp[i-1][k])+1; k=[1,2,...,j-1]，B[k]<B[j]=A[i]

else dp[i][j]=dp[i-1][j];

记录一下\(dp[i-1][j]\)最大的\(B[k]<B[j]\)，优化到\(O(n^2)\)

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int MAXN=510;

inline int read(){

	int x=0; char c=getchar();

	while(c<'0') c=getchar();

	while(c>='0') x=x*10+c-'0',c=getchar();

	return x;

}

int n,m,A[MAXN],B[MAXN];

int dp[MAXN][MAXN],g[MAXN][MAXN],pre[MAXN][MAXN];

inline void dfs(int i,int x){

	if(!x) return;

	dfs(i-1,pre[i][x]);

	if(pre[i][x]!=x)

		printf("%d ",B[x]);

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)

		A[i]=read();

	m=read();

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

		B[i]=read();

	for(int i=1;i<=n;++i){

		int k=0;

		for(int j=1;j<=m;++j){

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

			pre[i][j]=j;

			if(A[i]==B[j])

				dp[i][j]=dp[i-1][k]+1,pre[i][j]=k;

			if(B[j]<A[i]&&dp[i-1][j]>dp[i-1][k]) k=j;

		}

	}

	int Ans=0,k=0;

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

		if(dp[n][i]>Ans) Ans=dp[n][i],k=i;

	printf("%d\n",Ans);

	dfs(n,k);

	return 0;

}