专栏文章

题解：P10954 LCIS【数据暂时有误】

mmamingjun
P10954题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir4ozr0
此快照首次捕获于
2025/12/04 15:42
3 个月前
此快照最后确认于
2025/12/04 15:42
3 个月前
查看原文

题意：

给出两个数组a,ba,b. 求最长上升公共子序列.

解答

首先想到dpdp.

定义状态

表示第一个数组中前ii个数和第二个数组中前jj个数而且结尾为第二个数组中第jj个数结尾的LCISLCIS.

转移方程

当ai=bja_i=b_j时， 可以选择任意一个比bjb_j小的数做LCISLCIS中上一个数， 因为如果不选这个公共数时， 上一对公共数在选择这个数时也可以选到， 且区间更小， 故选这一对数更优.
当ai!=bja_i!=b_j时， 用ai−1,bja_{i-1},b_j的dpdp值，即寻找公共数对.
即dpi,j=max(dpi−1,k)(k<j)+1(ai=bj),dp_{i,j}=max(dp_{i-1,k})(k<j) + 1(a_i=b_j),
dpi,j=dpi−1,j(ai!=bj).dp_{i,j}=dp_{i-1,j}(a_i!=b_j).

codecode

CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, a[N], b[N], dp[N][N], ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (a[i] == b[j]) 
				for (int k = 1; k < j; k++){
					if (b[k] < b[j]) 
						dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
				}
			else dp[i][j] = dp[i - 1][j];
			ans = max(ans, dp[i][j]);
		}
	cout << ans << endl;
	return 0;
}
时间复杂度O(n3)O(n^3) 很明显过不了, 需要优化！
CPP
for (int k = 1; k < j; k++){
    if (b[k] < b[j]) 
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
}
这一部分时间复杂度较高, 可以优化.

最终codecode

CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, a[N], b[N], dp[N][N], ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) {
		int maxv = dp[i - 1][0];
		for (int j = 1; j <= n; j++) {
			if (a[i] == b[j]) dp[i][j] = maxv + 1;
			else dp[i][j] = dp[i - 1][j];
			if (b[j] < a[i]) maxv = max(maxv, dp[i - 1][j]);
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...