洛谷 P1439 分析（别看）
2026-07-09 16:21:14
发布于：河北
2阅读
0回复
0点赞
1 题目
要求两个序列的LCS
数据范围：
朴素LCS时间复杂度 需要优化
2 题目破题推导
按照这个步骤：
- 记录每个数字在P1里的位置，记作
- 把P2全部替换成pos里的值，得到新数组P2。相当于
- P2的LIS就是原来数组的LCS
那为什么？
因为最长公共子序列要求：
- 数字同时出现在P1，P2中
- 在P1的先后顺序和在P2的先后顺序一样
那我们就看为什么可以这样：
3 模型匹配
4 最终代码（禁止抄袭，仅用于参考）
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5 + 10;
int p1[N], p2[N];
int pos[N];
int dp[N];
int main(){
cin >> n;
for (int i = 1;i <= n;i++){
cin >> p1[i];
pos[p1[i]] = i;
}
for (int i = 1;i <= n;i++){
int x;
cin >> x;
p2[i] = pos[x];
}
int len = 0;
for (int i = 1;i <= n;i++){
if (p2[i] > dp[len]){
len++;
dp[len] = p2[i];
} else {
int l = lower_bound(dp + 1, dp + len + 1, p2[i]) - dp;
dp[l] = p2[i];
}
}
cout << len;
return 0;
}
这里空空如也
有帮助，赞一个