淄博阿雷网站建设公司,重庆易企云网络科技有限公司,外贸soho建站多少钱,怎么在网站里给图片做超链接题目描述
给出两个长度为 n 的整数序列#xff0c;求它们的最长公共子序列#xff08;LCS#xff09;的长度#xff0c;保证第一个序列中所有元素都不重复。
注意#xff1a; 第一个序列中的所有元素均不重复。 第二个序列中可能有重复元素。 一个序列中的某些元素可能不…题目描述
给出两个长度为 n 的整数序列求它们的最长公共子序列LCS的长度保证第一个序列中所有元素都不重复。
注意 第一个序列中的所有元素均不重复。 第二个序列中可能有重复元素。 一个序列中的某些元素可能不在另一个序列中出现。
输入样例
5
2 1 3 8 7
2 9 3 4 5输入样例
2数据范围 1 ≤ n ≤ 1 0 6 1≤n≤10^6 1≤n≤106, 序列内元素取值范围 [ 1 , 1 0 6 ] [1,10^6] [1,106] 最长上升子序列求法 O ( n l o g n ) O(nlogn) O(nlogn)
首先我们看看最长公共子序列的求解过程是什么样子的
A: 2 1 3 8 7 B: 2 9 3 4 5
ans {2, 3};
就是从B中按照下标从小到大的顺序从左至右去A中找相同的数字且在A中数字的下标也需要是递增的(也需要从左至右) 我们用另一种方式模拟这个过程 ① 我们先将A中的数字和下标存储在idx数组中idx[key] value,key 对应的是A中的值value对应的是A中元素值对应的下标
② 再按照坐标序遍历B中的元素找到其在A中的位置idx[key], 找到一个我们就处理这个元素的下标到f数组中将f数组维护为递增数组刚刚我们说到AB的子序列下标都需要是递增的;
f 数组维护的是B数组元素在A数组元素中的下标
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
C 代码
#include bits/stdc.husing namespace std;const int N 1e6 7;int idx[N], f[N];
int cnt;
int n;int find(int x) {int l 0, r cnt;while (l r) {int mid l r 1;if (f[mid] x) r mid;else l mid 1;}return l;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin n;memset(idx, -1, sizeof idx);for (int i 1; i n; i ) {int x;cin x;idx[x] i; // 记录数组中每个值的下标是多少}for (int i 1; i n; i ) {int x;cin x;int k idx[x];if (k -1) continue;if (k f[cnt]) f[ cnt ] k; // 如果当前下标大于f数组末尾元素下标就直接加入f数组else {int p find(k); // 找到大于等于k的第一个数的下标f[p] k; // 将下标的对应值替换掉}}cout cnt endl;return 0;
}
