python/TangDou/AcWing/LIS/LIS+LCS专题.md

LIS+LCS专题

一、基础题

AcWing 895. 最长上升子序列

时间复杂度 O(N^2)

状态表示 f[i]:以a[i]结尾的最长上升子序列长度

状态转移 f[i] = max(f[i], f[j] + 1)(a[i] > a[j])

初始值 f[i] = 1

解释：一个以i结尾的序列，最少可以是i自己，长度是1

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n;
int a[N], f[N];
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        f[i] = 1; // 一个以i结尾的序列，最少可以是i自己，长度是1
        for (int j = 1; j < i; j++)
            if (a[i] > a[j])                // i可以接在j后面
                f[i] = max(f[i], f[j] + 1); // 借力于j
        res = max(res, f[i]);
    }
    printf("%d", res);
    return 0;
}
    

AcWing 896. 最长上升子序列 II

数据量增大:N<=100000

思想 对于同样长度的子串，希望它的末端越小越好，这样后面更易扩展它,使数列更长。

时间复杂度 O(LogN*N)

状态表示 f[i]表示 长度为i 的递增子序列中，末尾元素最小 的是f[i]

答案 fl

特点与总结 ① f[]数组是一个单调上升的数组,这是二分的基础 ② 每个长度都争取替换掉前面记录数组中第一个大于等于自己的数字，以保证长度不变的情况下，数字最小。

学习方法 举栗子

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

int n, a[N];

// 数组模拟
int f[N], fl;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    // 1、首个元素
    f[0] = a[0];

    // 2、后续元素开始计算
    for (int i = 1; i < n; i++) {
        if (a[i] > f[fl])
            f[++fl] = a[i];
        else
            // 利用STL的二分，在f中查找第一个大于等于a[i]的值，并完成替换
            *lower_bound(f, f + fl, a[i]) = a[i];
    }
    // 栈内元素数量就是答案
    printf("%d\n", fl + 1);
    return 0;
}
  

AcWing 897. 最长公共子序列

状态表示 f[i][j]:a[]以i结尾，b[]以j结尾的 最长公共子序列长度

说明：没有说a[i]或者b[j]一定要出现在最长公共子序列当中！这个最长公共子序列，可能是a[]和b[]的一些前序组成的，a[i],b[j]也可能没有对结果产生贡献。

• 当a[i]==b[j]时，看一下两个字符串的前序，发现在少了a[i],b[j]后，转化为子问题f[i-1][j-1],问题转化为$f[i][j]=f[i-1][j-1]+1$

• 当a[i] \neq b[j]时：

  • 如果a[i]不产生贡献，那么把它干掉f[i-1][j]
  • 如果b[j]不产生贡献，那么把它干掉$f[i][j-1]$3

答案 f[n][m]

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    // 递推式出现f[i-1][j-1]，如果i,j从0开始会出现负值，所以下标从1开始
    cin >> n >> m >> a + 1 >> b + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j])
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    printf("%d", f[n][m]);
    return 0;
}

二、进阶题

AcWing 1017. 怪盗基德的滑翔翼

朴素O(N^2)版本

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n;    // 楼房的个数
int w[N]; // 楼房的高度数组
int f[N]; // LIS结果数组，DP结果

int main() {
    int T;
    cin >> T;
    while (T--) {
        // 保持好习惯，多组测试数据，记得每次清空结果数组
        memset(f, 0, sizeof f);
        int res = 0;

        cin >> n;
        for (int i = 1; i <= n; i++) cin >> w[i];

        // 从左到右,求一遍最长上升子序列[朴素O(N^2)版本]
        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++)
                if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }

        // 反向求解 LIS问题
        for (int i = n; i >= 1; i--) {
            f[i] = 1;
            for (int j = n; j > i; j--)
                if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }

        printf("%d\n", res);
    }
    return 0;
}

优化O(LogN*N)版本

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n;    // 楼房的个数
int a[N]; // 楼房的高度数组

// 数组模拟栈
int f[N], fl;
int g[N], gl;
int res;

int main() {
    int T;
    cin >> T;
    while (T--) {
        // 保持好习惯，多组测试数据，记得每次清空结果数组
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        fl = 0, gl = 0;

        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];

        // 正着求
        for (int i = 1; i <= n; i++) {
            if (a[i] > f[fl])
                f[++fl] = a[i];
            else
                *lower_bound(f + 1, f + 1 + fl, a[i]) = a[i];
        }

        // 反着求
        for (int i = n; i; i--) {
            if (a[i] > g[gl])
                g[++gl] = a[i];
            else
                *lower_bound(g + 1, g + 1 + gl, a[i]) = a[i];
        }
        // pk的最大结果
        res = max(fl, gl);
        // 输出
        printf("%d\n", res);
    }
    return 0;
}

AcWing 1014. 登山

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int n;    // 山的个数
int a[N]; // 山的高度数组
int f[N]; // 最长上升子序列
int g[N]; // 最长下降子序列
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 正向
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
    }
    // 反向
    for (int i = n; i >= 1; i--) {
        g[i] = 1;
        for (int j = n; j > i; j--)
            if (a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
    }

    // 每个点，都可能是两者相加的最大位置处，所以，需要枚举每个点，每个点都有资格参评最优点
    // 因为最终的那个中间点，左边计算了一次，右边又计算了一次，需要减1去重复
    for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);
    // 输出
    printf("%d\n", res);
    return 0;
}

AcWing 482. 合唱队形

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int n, a[N];
int f[N], fl, p1[N];
int g[N], gl, p2[N];

int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 正向
    f[++fl] = a[1];
    p1[1] = 1;

    for (int i = 2; i <= n; i++)
        if (a[i] > f[fl]) {
            f[++fl] = a[i];
            p1[i] = fl;
        } else {
            int t = lower_bound(f + 1, f + fl + 1, a[i]) - f;
            f[t] = a[i];
            p1[i] = t;
        }

    // 反向
    g[++gl] = a[n];
    p2[n] = 1;

    for (int i = n - 1; i >= 1; i--)
        if (a[i] > g[gl]) {
            g[++gl] = a[i];
            p2[i] = gl;
        } else {
            int t = lower_bound(g + 1, g + gl + 1, a[i]) - g;
            g[t] = a[i];
            p2[i] = t;
        }

    for (int i = 1; i <= n; i++) res = max(res, p2[i] + p1[i] - 1);

    printf("%d\n", n - res);
    return 0;
}

AcWing 1012. 友好城市 ① 数对 ② 左端点排序 ③ 对于右端点组成的数组，求最长上升子序列长度

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 5010;
PII a[N]; // 南岸和北岸的一对友好城市的坐标
int f[N]; // 记录以f[i]为结尾的一对友好城市时的，不产生交叉的最多城市对数
int n;    // n组友好城市
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n); // PII默认按第一维度first进行排序

    // LIS
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i].y > a[j].y)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d\n", res);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 5010;
PII a[N];     // 南岸和北岸的一对友好城市的坐标
int f[N], fl; // 数组模拟栈
int n;        // n组友好城市
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n);

    f[++fl] = a[1].y;
    for (int i = 2; i <= n; i++) {
        if (a[i].y > f[fl])
            f[++fl] = a[i].y;
        else
            *lower_bound(f + 1, f + 1 + fl, a[i].y) = a[i].y;
    }

    printf("%d\n", fl);
    return 0;
}

AcWing 1016. 最大上升子序列和

#include <bits/stdc++.h>
using namespace std;

// 最大上升子序列和
int n;
const int N = 100010;
int a[N];
int f[N];//以第i个元素结尾的最大子序列和
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        f[i] = a[i]; // 最大上升子序列（个数）这里是1,此处是a[i]
        for (int j = 1; j < i; j++)
            // 最大上升子序列（个数）这里是加1,此处是+a[i]
            if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
        res = max(res, f[i]);
    }
    printf("%d ", res);
    return 0;
}

魔改 最长上升子序列和

AcWing 1010. 拦截导弹

题目要求：但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

数组含义 q[],ql:已经创建了ql套导弹系统,q[i]中记录的是第i套导弹系统的最大拦截高度

举栗子,总结规律 q[0]:5 q[1]:6

举的这个栗子对吗？ 我们思考一下：原来有一套导弹拦截系统，上次的高度是5,现在第二颗导弹的高度是6，根据题目要求，它不能高于前一发的高度，所以只能再开一个导弹拦截系统，所以，第二个是6是正确的。

现在来了一个高度=4,根据上面的原则，可以接在5后面，也可以接在6后面，我们为了不浪费6,就选择了接在5后面，放到q[0]里，修改q[0]=4 q[0]:4 q[1]:6 原来的数组是单调上升的，修改后值也是在上下夹着中间的，也依然是单调上升的。

再比如： q[0]:4 q[1]:6 q[2]:7 现在来了一个a[i]=5,我们肯定要修改q[1]=5,变为：

q[0]:4 q[1]:5 q[2]:7 原来的数组是 单调上升 的，修改后也依然是 单调上升 的。

既然有这个规律，那么就可以使用二分快速查找大于等于a[i]的位置p了：

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int a[N], f[N]; // 每个导弹的高度，f[i]:以a[i]结尾的最长不升子序列长度
int q[N], ql;   // 需要ql套拦截系统，每个拦截系统最后一个拦截高度为q[i]
int n, res;

int main() {
    while (cin >> a[n]) n++;
    // 第一问
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] <= a[j]) // 如果前面的比当前的大，说明是不升序列
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    // 第二问
    for (int i = 0; i < n; i++) {
        int p = lower_bound(q, q + ql, a[i]) - q;
        if (p == ql) // 如果没有找到可以接在后面的导弹拦截系统，那么需要创建一套新的拦截系统
            q[ql++] = a[i];
        else
            q[p] = a[i]; // 否则就直接接到找到的第k套拦截系统的后面,那么，第k套拦截系统的最后一个拦截高度=q[k]=h[i]
    }
    // 输出最长不升序列长度,即：最多能拦截的导弹数
    printf("%d\n%d\n", res, ql);
    return 0;
}  

AcWing 187. 导弹防御系统

导弹拦截系统的拦截高度即可以 严格单调上升，又可以严格单调下降，此时，用LIS模型是无法解决问题的，考虑到n<50，可以用dfs+剪枝

#include <bits/stdc++.h>

using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;
int n;
int a[N];
int up[N], down[N];
int res;

// 本题关键字：贪心+爆搜

/*
 功能：暴搜所有可能，配合剪枝，找出最少的拦截系统数量
 u:  第几个导弹
 ul: 上升拦截系统的数量，配合up  数组使用
 dl: 下降拦截系统的数量，配合down数组使用
 */
void dfs(int u, int ul, int dl) {
    if (ul + dl >= res) return;  // 伟大的剪枝，不剪枝会TLE~,中途发现已经大于等于res的情况，就返回
    if (u == n) {                // 走完全程,收集答案
        res = min(res, ul + dl); // 因为上面的剪枝，把ul+dl>=res的全干掉了，能到这里的，都是<res的，都可以用来更新答案
        return;
    }

    // 放入上升序列
    int k = 0;
    // 如果把当前导弹使用上升序列的拦截系统进行拦截，那个选择哪个系统呢？
    for (k = 0; k < ul; k++)
        if (up[k] <= a[u]) break; // up[0],up[1],up[2],... 这样套拦截系统，其数值来讲，是递减的，因为是因为不能再拦截高度更低的才创建了一套新的拦截系统
    // 找出放到哪个拦截系统上去，结果为k

    int t = up[k]; // 尝试在第k套系统进行拦截第u个导弹,那么，第u个导弹的高度就是第k套系统的新高度
    up[k] = a[u];  // 问题是，我们也不一定非得让第u个导弹使用上升序列拦截系统，也可能使用下降序列拦截系统，所以需要记录当前值，回溯后，尝试下降序列拦截

    if (k < ul)                 // 如果当前这些套拦截系统中可以找到某一套进行拦截
        dfs(u + 1, ul, dl);     // 接到了某个队伍后面去了，修改队伍的最后最大值即可，队伍数量没有长大
    else                        // 如果当前这些套拦截系统中无法找到某一套进行拦截
        dfs(u + 1, ul + 1, dl); // 没有找到任何一个符合最后一个高度小于a[u]的队伍，只能多开一队，up数组长度长大1

    up[k] = t; // 回溯

    // ----------------------------------------------------------------------

    // 放入下降序列
    k = 0;
    for (k = 0; k < dl; k++)
        if (down[k] >= a[u]) break;

    t = down[k]; // 保留现场
    down[k] = a[u];
    if (k < dl)
        dfs(u + 1, ul, dl);
    else
        dfs(u + 1, ul, dl + 1);
    down[k] = t; // 回溯
}

int main() {
    while (cin >> n, n) { // 多套数据，输入n=0时停止
        for (int i = 0; i < n; i++) cin >> a[i];
        res = INF;    // 防御系统的最少数量
        dfs(0, 0, 0); // 开始深搜，更新res的值
        printf("%d\n", res);
    }
    return 0;
}

AcWing 272. 最长公共上升子序列

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;
// 通过了 10/13个数据
// O(n^3)
int main() {
    int n;
    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++) {
            // ① 二维DP打表的一般套路，都是可以直接从上一行继承的
            // ② 从题意出发，就是a中前i个数字，b中前j个数字，且以b[j]结尾的子序列中长度最大的
            // 那么，a中多整出一个数字来，最起码也是f[i-1][j]的值，不能更小
            f[i][j] = f[i - 1][j];
            // ③ 如果恰好 a[i]==b[j],那么就可以发生转移
            if (a[i] == b[j]) {
                int mx = 1; // 最起码a[i]==b[j]，有一个数字是一样嘀~
                // f[i-1]是肯定的了，问题是b的前驱在哪里？需要枚举1~j-1
                for (int k = 1; k < j; k++)
                    if (a[i] > b[k]) // j可以接在k后面，那么可能的最大值为f[i-1][k]+1
                        mx = max(mx, f[i - 1][k] + 1);
                // 更新答案
                f[i][j] = max(f[i][j], mx);
            }
        }
    int res = 0;
    // a数组肯定是火力全开到n就行，b数组中的位置就需要枚举了
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}

前面之所以把b[j]换成a[i],是因为方便现在考虑。

由于在枚举计算f[i][j]时，却用到的是和内层循环（即b[j]）无关的，只和外层循环（即a[i]）有关，而我们在计算f[i][j]，每次都要用到前j−1个数中小于a[i]的f[i-1][k]最大值，所以我们可以用一个变量mx不断更新它来保存前j−1的答案,就可以避免重复计算，从而降低时间复杂度。

O(N^2)

#include <bits/stdc++.h>

using namespace std;
const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;

// O(n^2)
// f[i][j]—集合：考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案
int main() {
    int n;
    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 mx = 1; // 如果a[i]==b[j],那么LICS最小是1.如果下面的循环中没有一个if被执行，则mx没使上        
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j]; // 先继承过来，现实含义：即使a[i]!=b[j],那么最长长度不会因为i的增加而变化，即f[i][j]=f[i-1][j]
            if (a[i] == b[j]) f[i][j] = mx;
            if (a[i] > b[j]) mx = max(mx, f[i - 1][j] + 1);
        }
    }

    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);

    return 0;
}

最长上升子序列 (LIS) 详解+例题模板 (全)