AcWing 3510. 最长公共子序列
原题链接
中等
作者:
0weili
,
2021-05-15 01:27:39
,
所有人可见
,
阅读 434
算法1
(找规律) $O(nlogn)$
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e6;
int map[maxn+1];
int n;
int main(void) {
scanf("%d", &n);
int t;
for(int i = 1; i <= n; i++) scanf("%d", &t), map[t] = i;
vector<int> v;
for(int i = 0; i < n; i++) {
scanf("%d", &t);
if(!map[t]) continue;
int idx = map[t];
if(v.empty() || idx > v.back()) v.push_back(idx);
else {
auto itr = lower_bound(v.begin(), v.end(), idx);
*itr = idx;
}
}
printf("%d\n", v.size());
return 0;
}
// 1. 遇到当前序列重复元素,忽略,因为是只可能是子集
// 2. 遇到序列中不包含的元素。
// 首先我们要知道,可能存在很多可能性,长度相同的序列可能有很多个。
// 但是同一个长度的序列,哪个能变得更长,只由最后一个元素决定,最后一个元素出现的位置越靠前,就可能变得更长。
// 所以,我们维持一个序列,当元素和末尾元素不同的时候,我们将他换到从左往右数,第一个索引比当前元素靠后的元素。
// 根据前面的分析,被替换元素是某个长度序列的最后元素,但由于当前元素的索引更靠前,变长的可能性更大