CH5101 LCIS（算法竞赛进阶指南，线性dp）

算法竞赛进阶指南，266页，线性dp
本题要点：
1、转态表示
f[i][j], 表示在 a[1] ~ a[i] 范围内，b[1] ~ b[j] 范围内，以b[j]结尾的LCIS 的长度
2、转态转移方程
a[i] != b[j], f[i][j] = f[i - 1][j];
a[i] == b[j], f[i][j] = 1 + max{f[i - 1][k], 0 <= k < j}

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 3010;
int f[MaxN][MaxN];	
int a[MaxN], b[MaxN];
int n;void solve()
{
    int ans = -1;//简化为二重循环for(int i = 1; i <= n; ++i){
    int val = 0;	//i固定，而且 b[j] < a[i] 的情况下， f[i - 1][k] 的最大值（0 <= k < j）if(b[0] < a[i])val = f[i - 1][0];for(int j = 1; j <= n; ++j){
    if(a[i] != b[j])	{
    f[i][j] = f[i - 1][j]; 	}else{
    f[i][j] = val + 1;}if(b[j] < a[i])		//不断维护最大值 val{
    val = max(val, f[i - 1][j]);}ans = max(ans, f[i][j]);}}printf("%d\n", ans);
}int main()
{
    scanf("%d", &n);for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);for(int i = 1; i <= n; ++i)scanf("%d", &b[i]);solve();return 0;
}/* 4 2 2 1 3 2 1 2 3 *//* 2 */