P10954 LCIS 题目解析

题目链接

思路

前置：弱化版

没什么好说的，设 \(f_{i,j}\) 表示 \(a\) 的前 \(i\) 个并且结尾为 \(b_j\) 的最长上升公共子序列。

定义 \(a_0=b_0=-\infty.\)

转移：

• \(a_i=b_j,f_{i,j}=\max_{k\in [0,j-1]\text{ 且 }b_k < a_i} f_{i-1,k}.\)
• 否则，\(f_{i,j}=f_{i-1,j}.\)

于是有了以下代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <climits>
#define N 3005
#define int long long
using namespace std;
int n,m,a[N],b[N],f[N][N],ans;
signed main(){
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
//	cin >> m;
	m = n; 
	for (int i = 1;i <= m;i ++) cin >> b[i];
	a[0] = b[0] = -LONG_LONG_MAX;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			if (a[i] == b[j]) {
				for (int k = 0;k < j;k ++)
					if (b[k] < a[i])
						f[i][j] = max(f[i - 1][k] + 1,f[i][j]);
			}
			else f[i][j] = f[i - 1][j];
			ans = max(ans,f[i][j]);
		}
	}
	cout << ans;
	return 0;
}

我们发现直接过掉了，但这样的时间复杂度是 \(\mathcal{O}(n^3)\) 的。

考虑免去一些重复的取 \(\max\) 值。

设决策 \(S(i,j)\) 为此次 \(f_{i,j}\) 的决策。

我们发现 \(b_k<a_i\) 中的 \(a_i\) 在某种程度上来讲是一个定值。

因此我们可以在枚举 \(i\) 的时候就把决策取入一个变量 \(mx\) 里面，当有满足 \(b_j<a_i\) 时，再加入进去（这是因为下一次 \(j+1\) 会有 \(j\) 的决策点 ）。

时间复杂度 \(\mathcal{O}(n^2)\)，正确地通过了本题。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <climits>
#define N 3005
#define int long long
using namespace std;
int n,m,a[N],b[N],f[N][N],ans;
signed main(){
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
//	cin >> m;
	m = n; 
	for (int i = 1;i <= m;i ++) cin >> b[i];
	a[0] = b[0] = -LONG_LONG_MAX;
	for (int i = 1;i <= n;i ++) {
		int mx = 0;
		if (b[0] < a[i]) mx = f[i - 1][0];
		for (int j = 1;j <= m;j ++) {
			if (a[i] == b[j]) f[i][j] = mx + 1;
			else f[i][j] = f[i - 1][j];
			ans = max(ans,f[i][j]);
			if (b[j] < a[i]) mx = max(mx,f[i - 1][j]);
		}
	}
	cout << ans;
	return 0;
}