题意
给定两个长度分别为 \(n,m\) 的序列 \(a,b\)，求这两个序列的最长公共递增子序列。
思路
最长公共递增子序列是最长上升子序列与最长公共子序列的结合，那么就需要将两者的思路相结合。
首先设计状态 \(dp_{i,j}\) 表示序列 \(a\) 的前 \(i\) 个组成的子序列与序列 \(b\) 的前 \(j\) 个组成的子序列的最长公共递增子序列。然后分类讨论。
若 \(a_i \ne b_j\)，则不能算贡献，且由于序列以 \(b_j\) 结尾，所以只能继承 \(dp_{i-1,j}\)，得转换方程：
若 \(a_i=b_i\)，则需找到一个 \(k\) 满足 \(1\le k <j\) 且 \(b_k<a_i\)，满足 \(dp_{i-1,k}\) 最大，然后算上一个 \(1\) 的贡献。当然，也可以选择继承 \(dp_{i-1,j}\)，这里需要对两者取最大值。得转换方程：
注意答案不一定是 \(dp_{n,m}\)，故需要一个变量来记录所有状态的最大值。
于是可以写出以下代码：
for(int i = 1 ; i <= n ; i ++) {for(int j = 1 ; j <= m ; j ++) {int maxx = 1;if(a[i] == b[j]) {for(int k = 1 ; k < j ; k ++) {if(a[i] > b[k]) maxx = max(maxx , dp[i - 1][k] + 1);}dp[i][j] = max(dp[i - 1][j] , maxx); } else dp[i][j] = dp[i - 1][j]; ans = max(ans , dp[i][j]);}}
时间复杂度为 \(O(nm^2)\)，所以超时也是自然的，现在考虑如何优化。
不难发现 \(k\) 这一层循环是没必要的，因为它遍历的区间 \([1,j-1]\) 在之前就已经遍历过了，所以再设计一个新的状态一起转移。
定义状态 \(dp_{i,j,0}\) 表示上述的最长公共递增子序列，\(dp_{i,j,1}\) 表示满足 \(1\le k <j\) 且 \(b_k<a_i\) 的最大 \(dp_{i-1,k,0}\)。
然后按原本的思路分类讨论。
若 \(a_i \ne b_j\)，转换方程为：
若 \(a_i=b_i\)，转换方程为：
若 \(a_i>b_j\)，转换方程为：
若 \(a_i\le b_j\)，转换方程为：
按照上述思路就可以得到以下代码：
for(int i = 1 ; i <= n ; i ++) {for(int j = 1 ; j <= m ; j ++) {if(a[i] == b[j]) {dp[i][j][0] = max(dp[i - 1][j][0] , dp[i][j - 1][1] + 1); } else dp[i][j][0] = dp[i - 1][j][0]; if(a[i] > b[j]) dp[i][j][1] = max(dp[i][j - 1][1] , dp[i - 1][j][0]);else dp[i][j][1] = dp[i][j - 1][1];ans = max(ans , dp[i][j][0]);}}
于是我们就成功地把时间复杂度从 \(O(nm^2)\) 优化成了 \(O(nm)\) 。
时间复杂度看起来无法继续优化，于是我们尝试优化空间复杂度。
不难发现，\(dp_{i,j,1}\) 是由 \(dp_{i,j-1,1}\) 转移而来，只与上一个状态有关，可以用滚动数组滚成零维即一个变量。
再来看 \(i\) 这一维，它同样只与上一个状态有关，所以也可以用滚动数组滚掉，于是就只剩下了 \(dp_j\)。
最终空间复杂度就由 \(O(nm)\) 优化成了 \(O(m)\)。
得到以下代码：
for(int i = 1 ; i <= n ; i ++) {int maxx = 0;for(int j = 1 ; j <= m ; j ++) {if(a[i] == b[j]) {dp[j] = max(dp[j] , maxx + 1); ans = max(ans , dp[j]);} if(a[i] > b[j]) maxx = max(maxx, dp[j]);}}
似乎无法继续优化了，这道题也就做完了。
全代码
#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define inui(a) a = read_unsigned_int()
#define in(a) a = read_int()
#define inp(a , b) a = read_int() , b = read_int()
#define inl(a) a = read_long_long()
using namespace std;
const int Size = 1 << 14;
const int N = 3e3 + 5;
const int inf = 0x3f3f3f3f;
inline char getc() {static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_unsigned_int() {int x = 0;char ch = getchar();while('9' < ch || ch < '0') ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus x;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
inline int read_long_long() {long long x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int a[N] , b[N] , dp[N];
signed main() {//cin_fast;int t;in(t);while(t --) {memset(dp , 0 ,sizeof(dp));int n;in(n);for(int i = 1 ; i <= n ; i ++) in(a[i]);int m;in(m);for(int i = 1 ; i <= m ; i ++) in(b[i]);int ans = 0;for(int i = 1 ; i <= n ; i ++) {int maxx = 0;for(int j = 1 ; j <= m ; j ++) {if(a[i] == b[j]) {dp[j] = max(dp[j] , maxx + 1); ans = max(ans , dp[j]);} if(a[i] > b[j]) maxx = max(maxx, dp[j]);}}cout<<ans<<'\n';}I_love_Foccarus 0;
}