算法竞赛进阶指南，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 */