LCS、LIS

LCS是最长公共子序列的表示:
题目链接
LCS、LIS
代码也十分简单就不敲了。

LIS是最长上升子序列的英文缩写。

(动态规划) O(n2)O(n2)
状态表示:f[i]表示从第一个数字开始算,以w[i]结尾的最大的上升序列。(以w[i]结尾的所有上升序列中属性为最大值的那一个)

状态计算(集合划分):j∈(0,1,2,…,i-1), 在w[i] > w[j]时,
f[i] = max(f[i], f[j] + 1)。
有一个边界,若前面没有比i小的,f[i]为1(自己为结尾)。

最后在找f[i]的最大值。

时间复杂度
O(n2) 状态数(n) * 转移数(n)

之后就是两种的一种结合。
题目如下:

给出两个长度为 n 的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。

注意:

第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。
输入格式
第一行包含一个整数 n。

接下来两行,每行包含 n 个整数,表示一个整数序列。

输出格式
输出一个整数,表示最长公共子序列的长度。

数据范围
1≤n≤106,
序列内元素取值范围 [1,106]。

输入样例1:
5
1 2 3 4 5
1 2 3 4 5
输出样例1:
5
输入样例2:
5
1 2 3 5 4
1 2 3 4 5
输出样例2:
4

因为第一个序列的元素并不重复,所以第二个序列元素对应在第一个序列相同元素的下标是不重复的,而子序列的定义是,组成子序列的元素在原数组的下标一定是严格单调递增的。所以可以转换为求最长上升子序列,而最长上升子序列还有一种二分贪心优化的方法。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 +10;
int a[N],q[N];
int n;
int main()
{
    memset(a, -1, sizeof a);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int x;
        scanf("%d",&x);
        a[x] = i;
    }
    q[0] = -1;
    int tt = 0;
    for (int i = 0; i < n; i ++ ){
        int x;
        scanf("%d", &x);
        int k = a[x];
        if (k==-1) continue;
        int l=0,r= tt;
        while (l<r){
            int mid = (l+r+1)>>1;
            if (q[mid]<k) l = mid;
            else
            r = mid-1;
        }
        q[r+1] = k;
        tt = max (tt,r+1);
    }
    printf("%d",tt);
    return 0;
}
上一篇:python刷题笔记(3)


下一篇:实验四