我们学过最长升序列（Longest Increasing Subsequence，简称LIS）和最长公共子序列（Longest Common Subsequence，简称LCS）（没错之前两篇博客就是为这篇准备的……），那么如果我们要求最长公共上升子序列（Longest Increasing Common Subsequence，简称LICS或者LCIS）呢？
（建议阅读本文之前先看看LCS。）
例题：Greatest Common Increasing Subsequence （HDU）
O（N³）的动态规划
一开始想到的肯定是结合LIS和LCS，如何结合？回忆一下LCS的定义：F[i][j]表示A的第i位及之前 的子序列与 B的第j位及之前 的子序列，这两段序列的LCS长度。注意，A中1到i段与B中1到j段LCS不一定取了i或j。这就很麻烦了：如何判断下一个取的元素大于LCS的最后一个元素，也就是如何判断取下一个元素后序列是不是升的呢？这时候不得不重新考虑DP的定义了。
由于要标记LCS的最后一个元素，不妨像LIS一样，定义F[i][j]表示A的第i位及之前 的子序列与 B的第j位及之前 的子序列，这两段序列的LCS长度，其中B[j]是LCS的最后一个元素。与LCS一样枚举i、j，讨论几种情况：
- A[i]>B[j]：既然这位上可以取，因为第一维定义时没有规定A[i]必取，所以之前的LICS长度第一维必然是i-1；然而第二维规定了B[j]必取，所以LICS长度第二维不一定是j-1，因为如果取F[i-1][j-1]意味着j-1必取了。所以应该枚举一个k∈[1,j-1]，在F[i-1][k]中取最大值+1就是F[i][j]了。
- A[i]<B[j]：由于B[j]是最后一个，所以不能直接像LCS一样F[i][j]=max(F[i-1][j],F[i][j-1])；应该是F[i][j]=F[i-1][j]，因为这时求得的LCS根本没变，B[j]一定与A[1...i-1]中一个元素相等，不考虑A[i]照样能得出最优解。 所以得出转移方程：
F[i][j]=F[i-1][j]; (a[i]≤b[j])
F[i][j]=max(F[i-1][k])+1; (b[k]<b[j] && 1≤k≤j-1)
这样写的时间复杂度是O（N³），（在上面那道例题中）似乎并不能达到满分。能不能优化呢？
如何优化成O（N²）？
仔细观察，这个DP慢就慢在k这层循环。如果我们把k这层循环拿掉该多好！（因为N²个子问题是不可避免的，所以只能优化这层循环……）观察转移方程，如果我们能把max(F[i-1][k])+1提前处理出来就好了！但是有个重要的条件：b[k]<b[j]。k在不断变化，j也在不断变化，有这个条件的限制就难以构造了……
看看前面，a[i]=b[j]！所以这个条件就变成b[k]<a[i]！ 我们在外层循环枚举i，在里面一层循环求答案只与i-1有关，i就相当于是不再变化的！这样就可以构造个lst数组（last的缩写），存储max(F[i-1][k])，也可以判断这个条件了！
lst[j-1]=max(lst[j-2],f[i][j-1]); (b[j-1]<a[i+1])
lst[j-1]=lst[j-2]; (b[j-1]≥a[i+1])
加上这个优化，这题就能AC了~贴上代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=505;
int t,n,m,a[maxn],b[maxn],f[maxn][maxn],lst[maxn];
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline int max(int x,int y){
if (x>y) return x; else return y;
}
int main(){
freopen("lics.in","r",stdin);
freopen("lics.out","w",stdout);
t=read();
while (t--){
n=read();
for (int i=1;i<=n;i++) a[i]=read();
m=read();
for (int i=1;i<=m;i++) b[i]=read();
int ans=0;
memset(f,0,sizeof(f));memset(lst,0,sizeof(lst));
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (a[i]==b[j]) f[i][j]=lst[j-1]+1; else f[i][j]=f[i-1][j];
if (j!=1){
if (b[j-1]<a[i+1]) lst[j-1]=max(lst[j-2],f[i][j-1]);
else lst[j-1]=lst[j-2];
}
if (f[i][j]>ans) ans=f[i][j];
}
if (b[m]<a[i+1]) lst[m]=max(lst[m-1],f[i][m]); else lst[m]=lst[m-1];
}
printf("%d\n",ans);
if (t) printf("\n");
}
return 0;
}