最长公共上升子序列（LCIS）
原题链接：CodeForces、洛谷
时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB描述
给定两个整数序列，写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候，我们将长度 \(N\) 的序列 \(S_1,S_2,...,S_N\) 称为长度为 \(M\) 的序列 \(A_1,A_2,...,A_M\) 的上升子序列：
存在 \(1≤i_1<i_2<...<i_N≤M\)，使得对所有 \(1≤j≤N\)，均有 \(S_j=A_{i_j}\)，且对于所有的 \(1≤j<N\)，均有 \(S_j<S_{j+1}\)。输入描述
每个序列用两行表示，
第一行是长度 \(M(1≤M≤500)\)
第二行是该序列的 \(M\) 个整数 \(A_i(−2^{31}<A_i<2^{31})\)输出描述
在第一行，输出两个序列的最长上升公共子序列的长度 \(L\)。
在第二行，输出该子序列。
如果有不止一个符合条件的子序列，则输出任何一个即可。用例输入 1
5 1 4 2 5 -12 4 -12 1 2 4用例输出 1
2 1 4提示
\(1≤M≤500\)
\(−2^{31}<A_i<2^{31}\)
解析
如何求 LCIS 的长度可以参考 AcWing 的题解，这里只讲怎么求取并输出这个序列。
用一个 pair<int,int> 的二维数组 \(pre_{i,j}=\{x,y\}\) 来记录 \(f_{i,j}\) 由哪一个 \(f_{x,y}\) 更新而来，最后找到使 \(f_{n,ans}\) 最大的 \(ans\) 以后顺着 \(pre_{n,ans}\) 一路递归回去就可以找到更新出这个最大值的全部路径。
在每次更新 \(f_{i,j}\) 的时候同时更新 \(pre_{i,j}\)。
（此处不算错误但是冗余的想法）
因为在 \(a_i=b_j\) 的时候也可以不加上 \(a_i\)，所以在进入 \(k\) 的循环之前还需要将 \(f_{i,j}\) 赋值为 \(f_{i-1,j}\)，\(pre_{i,j}\) 也同步赋值为 \(pre_{i-1,j}\)，当然如果 \(f_{i-1,j}\) 还没有 \(1\) 大，则可以只把 \(f_{i,j}\) 赋为 \(1\)。
但是 \(f_{i-1,j}\) 由 \(f_{i-2,l},l \in [1,j-1]\) 更新而并 \(+1\)，且必须保证 \(b_j>b_l\)；当扫描 \(f_{i-1,k},k \in [1,j-1]\) 的时候，因为其已经包含了 \(f_{i-2,j-1}\)（因为 \(f\) 的第一维表示“前 \(i\) 个”），所以它 \(+1\) 以后答案不会小于 \(f_{i-1,j}\)。由此，将 \(f_{i,j}\) 赋值为 \(f_{i-1,j}\) 后不会得到更优解，只用在进入循环前把 \(f_{i,j}\) 赋值为 \(1\) 即可
（当然你将 \(f_{i,j}\) 赋值为 \(f_{i-1,j}\) 了也没问题，在某些情况下（例如用 \(pre_{f_{i-1,k},j}\) 来表示前继时）反而必须用上面先赋为 \(f_{i-1,j}\) 的写法来避免出现同一个 \(pre\) 被多次更新导致指向错误的情况发生，但是用 \(pre_{i,j}\) 来表示就完全不可能产生奇奇妙妙的多次更新错误）。
注意，因为 \(f_{i,j}\) 表示的是“\(a_{1 \sim i},b_{1 \sim j}\) 且以 \(b_j\) 结尾的最长公共上升子序列长度”，并没有要求一定以 \(a_i\) 结尾，所以输出的时候不能输出 a[pre[i][j].first]，但因为保证一定以 \(b_j\) 结尾，所以可以输出 b[pre[i][j].second]
代码
注释掉的即为上面说的冗余想法
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=505;
int n,m,a[N],b[N];
int f[N][N];
pair<int,int> pre[N][N];
void DFS(pair<int,int> x)
{
if(x.first&&x.second)
{
DFS(pre[x.first][x.second]);
printf("%d ",b[x.second]);
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])
{
// if(f[i-1][j]>1) f[i][j]=f[i-1][j],pre[i][j]=pre[i-1][j];
// else f[i][j]=1;
f[i][j]=1;
for(int k=0;k<j;k++)
if(b[k]<a[i])
{
if(f[i-1][k]+1>f[i][j])
{
f[i][j]=f[i-1][k]+1;
pre[i][j]={i-1,k};
}
}
}
else
{
f[i][j]=f[i-1][j];
pre[i][j]=pre[i-1][j];
}
}
int ans=0;
for(int i=1;i<=m;i++)
if(f[n][i]>f[n][ans]) ans=i;
printf("%d\n",f[n][ans]);
DFS({n,ans});
return 0;
}