参考《算法竞赛进阶指南》、AcWing题库

895. 最长上升子序列

题目描述

给定一个长度为 NN 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 NN。

第二行包含 NN 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤10001 \le N \le 1000，
−109≤数列中的数≤109-10^9 \le 数列中的数 \le 10^9

输入样例：

1
2
7
3 1 2 1 8 5 6

输出样例：

1
4

算法分析

3.jpg

贪心写法见 1010.拦截导弹

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], f[N];
int main() {
    int n ;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
    }
    cout << ans;
}

1017. 怪盗基德的滑翔翼

题目描述

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。

而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。

不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。

初始时，怪盗基德可以在任何一幢建筑的顶端。

他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。

因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。

他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。

请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

输入格式

输入数据第一行是一个整数K，代表有K组测试数据。

每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出。

输出格式

对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

数据范围

1≤K≤1001 \le K \le 100,
1≤N≤1001 \le N \le 100,
0<h<100000 < h < 10000

输入样例：

1
2
3
4
5
6
7
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

输出样例：

1
2
3
6
6
9

算法分析

3.png

这题选比较裸的一道题，我们先来分析一下题目

首先，求一个高度递减的楼房子序列长度最大，其实就是求一个最长下降子序列

然后，这个怪盗基德老哥可以选择任意楼房作为起始位置，接着选择一个方向飞到尽头

于是，我们可以画出如下三种情况：

IMG_330A8B5301F2-1.jpeg

对于左边界情况来说，其实就是中间位置的左侧序列长度为 00 的情况；右边界情况同理

所以，我们只需讨论中间情况即可（两侧边界情况是该情况的子集）

于是，对于任意位置 xx，我们分别需要求出以他为右端点的最长上升子序列，以及作为左端点的最长下降子序列

而DP中经典的最长上升子序列模型f[i]的状态表示就是以i为端点的最长上升子序列

由此我们通过线性DP，可以求出任一点的左侧最长上升和右侧最长下降

两者取一个 Max\mathrm{Max}，就是以该点作为起点的最佳飞行方向的最大长度

然后再枚举所有点取一个 Max\mathrm{Max}，就是最佳起点的最大长度，便是本题的答案

这题的DP模型就是经典的最长上升子序列

03_怪盗基德的滑翔翼.png

{状态表示fi{集合:以第i个位置作为最长上升子序列的右端点的方案属性:方案的子序列长度最大Max状态转移fi=max{1,max{∑j=1i−1fj}+1}(ai>aj)\begin{cases} 状态表示f_i \begin{cases} 集合: 以第i个位置作为最长上升子序列的右端点的方案 \\ 属性: 方案的子序列长度最大 Max \end{cases} \\ 状态转移 f_i = max\{1, max\{\sum_{j=1}^{i-1}f_j\}+1\} \quad (a_i > a_j) \end{cases}

Solution

正向上升 + 反向下降

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
const int N = 110;
int h[N], f[N];
int main() {
    int k;
    cin >> k;
    while (k--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> h[i];
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = 1;
            for (int j = 1; j < i; ++j) {
                if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
            }   
            ans = max(ans, f[i]);
        }
        for (int i = n; i >= 1; --i) {
            f[i] = 1;
            for (int j = n; j > i; --j) {
                if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
        }
        cout << ans << endl;
    }
}

正向上升 + 正向下降

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int h[N], fUp[N], fDown[N];
int main() {
    int k;
    cin >> k;
    while (k--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> h[i];
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            fUp[i] = fDown[i] = 1;
            for (int j = 1; j < i; ++j) {
                if (h[j] < h[i]) fUp[i] = max(fUp[i], fUp[j] + 1);
                if (h[j] > h[i]) fDown[i] = max(fDown[i], fDown[j] + 1);
            }   
            ans = max({ans, fUp[i], fDown[i]});
        }
        cout << ans << endl;
    }
}

1014. 登山

题目描述

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

2≤N≤10002 \le N \le 1000

输入样例：

1
2
8
186 186 150 200 160 130 197 220

输出样例：

1
4

算法分析

此题和上题怪盗基德的滑翔翼有着异曲同工之妙

上题求的是从一个点开始，朝向一个方向求一个最长下降子序列

本题则是让我们求一个先上升后下降的最长子序列，具体如下图所示

IMG_67CBC7A02142-1.jpeg

当然也和上题一样存在边界情况，即最优解答案可以是一个单调下降子序列或单调上升子序列

这种边界情况一样是先上升后下降的最长子序列的子集，因此不用额外讨论

常规做法

一种做法是和上题一样，先做一遍最长上升，再做一遍最长下降

然后根据状态表示的特性，将两个状态的值相加，取一个 Max\mathrm{Max} 就是 先上升后下降的最长子序列的长度

状态机模型DP

利用状态机模型DP解决最长xxx子序列模型的方法

xxx可以是先上升后下降，或者先上升后下降再上升，或者先上升后下降再上升再下降 ···

回到本题，我们就可以先利用状态机模型进行分析，具体如下：

IMG_375680990BCC-1.jpeg

对于本题来说，当前状态如果是上升状态，则他下一个阶段可以维持上升状态，或者变成下降状态

而对于已经处于下降状态来说的状态，下一个阶段只能继续维持下降状态

{状态表示fi,j{集合:以第i个位置作为当前子序列的右端点，且当前状态为j属性:方案的子序列长度最大Max状态转移{fi,0=max{∑fk,0}+1fi,1=max{∑fk,0,∑fk,1}+1\begin{cases} 状态表示f_{i,j} \begin{cases} 集合: 以第i个位置作为当前子序列的右端点，且当前状态为j \\ 属性: 方案的子序列长度最大 Max \end{cases} \\ 状态转移 \begin{cases} f_{i,0} = max\{\sum f_{k,0}\}+1 \\ f_{i,1} = max\{\sum f_{k,0}, \sum f_{k,1}\} + 1 \end{cases} \end{cases}

初始状态: f[0][0]和f[0][1]

目标状态: f[i][0]和f[i][1]

更近一步了解这类模型的话，可以做一下这道题 AcWing 3549. 最长非递减子序列

Solution

状态机模型DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int h[N], f[N][2];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = f[i][1] = 1;
        for (int j = 1; j < i; ++j) {
            if (h[j] < h[i]) f[i][0] = max(f[i][0], f[j][0] + 1);
            if (h[j] > h[i]) f[i][1] = max({f[i][1], f[j][0] + 1, f[j][1] + 1});
        }
        ans = max({ans, f[i][0], f[i][1]});
    }
    cout << ans;
}
常规LIS动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 1010;
int h[N], fU[N], fD[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) {
        fU[i] = 1;
        for (int j = 1; j < i; ++j) 
            if (h[j] < h[i]) fU[i] = max(fU[i], fU[j] + 1);
    }
    for (int i = n; i >= 1; --i) {
        fD[i] = 1;
        for (int j = n; j > i; --j) 
            if (h[j] < h[i]) fD[i] = max(fD[i], fD[j] + 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, fU[i] + fD[i] - 1);
    cout << ans;
}

482. 合唱队形 - AcWing题库

题目描述

NN 位同学站成一排，音乐老师要请其中的 (N−K)(N-K) 位同学出列，使得剩下的 KK 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 KK 位同学从左到右依次编号为 1，2…，K1，2…，K，他们的身高分别为 T1，T2，…，TKT_1，T_2，…，T_K，  则他们的身高满足 T1<…<Ti>Ti+1>…>TK(1≤i≤K)T_1 < … < T_i > T_{i+1} > … > T_K(1 \le i \le K)。

你的任务是，已知所有 NN 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式

输入的第一行是一个整数 NN，表示同学的总数。

第二行有 NN 个整数，用空格分隔，第 ii 个整数 TiT_i 是第 ii 位同学的身高(厘米)。

输出格式

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

数据范围

2≤N≤1002 \le N \le 100,
130≤Ti≤230130 \le T_i \le 230

输入样例：

1
2
8
186 186 150 200 160 130 197 220

输出样例：

1
4

算法分析

本题的要求是，我们对原数组删去尽量少的数字，构成该类型序列

我们知道，一个序列的子序列，就是通过删去原序列中部分的元素后构成的

因此，找到满足该类型序列，最少需要删除的元素数量 ≡\equiv 找到满足该类型序列，最长子序列的长度

通过这个等价转换，本题就完全转换成了上一题了

Solution

状态机模型DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int h[N], f[N][2];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = f[i][1] = 1; 
        for (int j = 1; j < i; ++j) {
            if (h[j] < h[i]) f[i][0] = max(f[i][0], f[j][0] + 1);
            if (h[j] > h[i]) f[i][1] = max({f[i][1], f[j][0] + 1, f[j][1] + 1});
        }
        ans = max({ans, f[i][0], f[i][1]});
    }
    cout << n - ans;
}
常规最长上升子序列DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int h[N], f[N][2];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = f[n - i + 1][1] = 1; 
        for (int j = 1; j < i; ++j) {
            if (h[j] < h[i]) f[i][0] = max(f[i][0], f[j][0] + 1);
            if (h[n - j + 1] < h[n - i + 1]) f[n - i + 1][1] = max(f[n - i + 1][1], f[n - j + 1][1] + 1);
        }
    }
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i][0] + f[i][1] - 1);
    cout << n - ans;
}

1012. 友好城市

题目描述

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式

第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围

1≤N≤50001 \le N \le 5000,
0≤xi≤100000 \le x_i \le 10000

输入样例：

1
2
3
4
5
6
7
8
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例：

1
4

算法分析

本题的背景是一个造桥项目，初始给定我们 nn 座打算建造的桥

每座桥有两个参数 x1x_1 和 x2x_2，表示该桥一头连接在上岸坐标为x1x_1的地方，一头连在下岸坐标为x2x_2的地方

题目要求我们找出一种建桥方案，使得在所有建造的桥不相交的前提下，建造尽可能多的桥

求出该方案的造桥数量

具体的情况用文字可能不太好解释，这里画了一张图方便大家理解

IMG_C28908166361-1.jpeg

红色虚线表示初始提供的打算建造的桥

我们要找出的方案是在不相交的前提下的最大建桥数量

也就是上面的绿线连接而成的方案

这就是本题的大致意思

我们先想一下暴力怎么做

很容易想到，我们可以枚举所有的方案，然后检查方案是否合法，如果合法就考虑是否能够更新最大值答案

这么做的时间复杂度是 O(2n)O(2^n)，而 nn 的数据范围是 50005000，毫无疑问会超时。

所以，我们就需要找出一些性质进行优化

既然是要暴力枚举，我们可以考虑一个枚举方案，按照上岸的坐标从小到大来枚举

然后我们只需关心下岸的坐标之间有何关系即可

于是，可以轻易发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的

具体见下图：

蓝色表示该方案按照上坐标从小到大先选出来的桥

红色表示该方案的下一座桥的下坐标不是从小到大的，绿色表示是从小到大的

IMG_8E9F9D967AE9-1.jpeg

因此，该方案中，在上坐标排序的情况下，下坐标次序不是从小到大的，则必然不合法（会有相交）

于是，这题就变成了：桥以上坐标从小到大排序后，找出下坐标的最长上升子序列长度

我们可以用pair或者struct先把所有的桥存下来，然后按照上坐标排序

再然后，下坐标就构成了一个序列，我们只需找出该序列的最长上升子序列的长度，就求出本题的答案了

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
pair<int,int> city[N];
int f[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> city[i].first >> city[i].second;
    sort(city + 1, city + 1 + n);//注意！！！下标从1开始，排序时要 + 1
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (city[j].second < city[i].second) f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
    }
    cout << ans;
}

1016. 最大上升子序列和

题目描述

一个数的序列 bib_i，当 b1<b2<…<bSb_1<b_2<…<b_S 的时候，我们称这个序列是上升的。

对于给定的一个序列(a1,a2,…,aNa_1,a_2,…,a_N)，我们可以得到一些上升的子序列(ai1,ai2,…,aiKa_{i_1},a_{i_2},…,a_{i_K})，这里1≤i1<i2<…<iK≤N1≤i_1<i_2<…<i_K≤N。

比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。

这些子序列中和最大为18，为子序列(1,3,5,9)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

输入格式

输入的第一行是序列的长度N。

第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。

输出格式

输出一个整数，表示最大上升子序列和。

数据范围

1≤N≤10001 \le N \le 1000

输入样例：

1
2
7
1 7 3 5 9 4 8

输出样例：

1
18

算法分析

07_最长上升子序列和.png

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
const int N = 1010;
int a[N], f[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = a[i];
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]);
        }
        ans = max(ans, f[i]);
    }
    cout << ans;
}

1010. 拦截导弹（贪心二分LIS）

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

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

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行，输入导弹依次飞来的高度。

输出格式

第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 3000030000 的正整数，导弹数不超过 10001000。

输入样例：

1
389 207 155 300 299 170 158 65

输出样例：

1
2
6
2

算法分析

Dilworth定理转化

Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度
Dilworth定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度

通俗解释： 把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度（LIS)。

  • 最长上升子序列的长度 == 最少的非升子序列的划分数

  • 最长非升子序列的长度 == 最少的上升子序列的划分数

  • 最长下降子序列的长度 == 最少的非降子序列的划分数

  • 最长非降子序列的长度 == 最少的下降子序列的划分数

求最少划分数的一种贪心
  • 将序列划分成最少的非升子序列
  • 贪心思路：较大的数作为末尾元素的子序列比较小的数作为末尾元素的子序列更好，更容易接上
  • 贪心步骤：
    • 开一个last[]记录所有下降子序列末尾元素，last[]一开始是空集，长度为0
    • 遍历原序列中的每个数，对于当前这个数x：
      • 情况1：在last[]中若找不到≥大于等于当前数x的数，接不上，需要新开非升序列，即扩大last[]长度并记录当前数x，因为last[]单调上升，即对应x > last[最后数的下标]
      • 情况2：在last[]中可以找到≥大于等于当前数x的最小的数 last[idx]，则将当前数x接在数last[idx]作为末尾元素的子序列，因为last[idx]记录的是该子序列的末尾元素，故将last[idx]更新为x，即last[idx] = x
    • 最终last[]数组的长度即为最少划分数，且last[]中存储的是原序列的最长上升子序列
  • 可以证明last[]必定是一个单调上升的数组
    • 一开始last[]是空集，空集也是单调的一种
    • 对于每个数x要记录到last[]时，last[]中有不等式a > b > c，假设b是所有大于等于≥数x的那个最小的数，则有不等式a > b ≥ x > c
    • 覆盖之后就会变成a > x > c，并不改变last[]的单调性，且last[]是每次用一个较小的数覆盖一个较大的数作为末尾元素更新到last[]。如果无法覆盖更新，必须扩大last[]，也就表示此时新增x比所有末尾元素都大。故last[]随下标增大元素值也越大，因此last[]是单调上升的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> last_of_each_LNIS; 

        for (auto x : nums) {
            if (last_of_each_LNIS.empty() || x > last_of_each_LNIS.back()) last_of_each_LNIS.push_back(x);
            else *lower_bound(last_of_each_LNIS.begin(), last_of_each_LNIS.end(), x) = x;
        }

        return last_of_each_LNIS.size();
    }
};
求最长上升子序列的一种贪心
  • 贪心思路：对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长
  • 贪心步骤：
  • 维护数组last[]，last[i]存的是所有长度为i的上升子序列中，末尾元素最小的子序列的末尾元素
  • last[]一开始是空集，长度为0
  • 遍历原序列中的每个数x，对于当前数x
    * 如果数x大于当前最长上升子序列的末尾元素，即x > last[当前最长LIS的长度]，就把数x接到当前最长的LIS后面，即last[++当前最长LIS的长度] = x
    * 否则，利用数x更新last[]数组：在last[]数组中找到大于等于x的最小的数last[idx]，也即首个大于等于x的数，更新last[idx] = x，肯定能找到，起码last[当前最长LIS的长度]就满足
  • 可以证明last[]必定是一个严格单调上升的数组
    • 一开始last[]是空集，空集也是单调的一种
    • 对于每个数x要记录到last[]时，last[]中有不等式a < b < c，c是last[]数组最后的一个数
      • 如果当前数x > c，将数x加入last[]数组末尾，则有a < b < c < x，仍然单调上升
      • 如果当前数x = c，则c就是大于等于x的最小的数，更新后有a < b < x，仍然单调上升
      • 如果当前数x < c，找到大于等于x的最小的数，因为last[]是单调上升的，首个大于等于x的数即为最小的数，假设为b，更新后有a < x < c，仍然单调上升
    • 故last[]始终单调上升，且是严格上升
  • 查找[begin, end)范围里首个大于等于x的数可以用lower_bound(begin, end, x)，找到则返回指向目标的迭代器，否则返回end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> last_of_each_len_lis;

        for (auto x : nums) {
            if (last_of_each_len_lis.empty() || x > last_of_each_len_lis.back()) last_of_each_len_lis.push_back(x);
            else *lower_bound(last_of_each_len_lis.begin(), last_of_each_len_lis.end(), x) = x;
        }

        return last_of_each_len_lis.size();
    }
};
注意两种贪心数组的区别
  • 最少划分数贪心是记录每个子序列末尾的数，last 中每个数都代表划分的一个子序列的末尾元素，一共划分了last.size()个子序列
  • 最长子序列长度贪心是记录每种长度的子序列的末尾最小值，last[i] = 所有长度为 i 的上升子序列中，最小的末尾元素

Solution

运用Dilworth定理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include  <iostream>
using namespace std;
const int N = 1010;
int h[N], f[N][2];
int main() {
    int n = 0;
    while (cin >> h[n]) ++n;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; ++i) {
        f[i][0] = f[i][1] = 1;
        for (int j = 0; j < i; ++j) {
            if (h[j] >= h[i]) f[i][0] = max(f[i][0], f[j][0] + 1);
            if (h[j] < h[i]) f[i][1] = max(f[i][1], f[j][1] + 1);
        }
        ans1 = max(ans1, f[i][0]);
        ans2 = max(ans2, f[i][1]);
    }
    cout << ans1 << endl << ans2;
}
两种贪心：长度 + 划分数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int h[N], last1[N], last2[N], idx1, idx2;
int main() {
    int n = 0;
    while (cin >> h[n]) ++n;
    //最长非升子序列 = 最少的上升子序列的划分数
    //划分数和求长度各有一种贪心写法
    //这里直接用贪心求长度
    //last1[i] = 所有长度为 i 的非升子序列中末尾元素最小的那个子序列的末尾值
    for (int i = 0; i < n; ++i) {
        if (i == 0 || h[i] <= last1[idx1 - 1]) last1[idx1++] = h[i];//如果可以接在最长的子序列后面就接上
        else *upper_bound(last1, last1 + idx1, h[i], greater<int>()) = h[i];//找到第一个严格小于h[i]的数，替换
    }
    cout << idx1 << endl;
    
    //最少的非升子序列的划分数 = 最长上升子序列
    //划分数和求长度各有一种贪心写法
    //这里直接用贪心求划分数
    //last2[] = 非升子序列的末尾元素，没有长度 i 的限制
    for (int i = 0; i < n; ++i) {
        if (i == 0 || h[i] > last2[idx2 - 1]) last2[idx2++] = h[i];//如果所有末尾元素都比当前数小，接不上，新开一个非升序列
        else *lower_bound(last2, last2 + idx2, h[i]) = h[i];
    }
    cout << idx2 << endl;
}

187. 导弹防御系统

题目描述

为了对抗附近恶意国家的威胁，RR 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 33 和高度为 44 的两发导弹，那么接下来该系统就只能拦截高度大于 44 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 nn，表示来袭导弹数量。

第二行包含 nn 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0n=0 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围

1≤n≤501 \le n \le 50

输入样例：

1
2
3
5
3 5 2 4 1
0

输出样例：

1
2

样例解释

对于给出样例，最少需要两套防御系统。

一套击落高度为 3,43,4 的导弹，另一套击落高度为 5,2,15,2,1 的导弹。

算法分析

搜索顺序分为两个阶段：

  • 从前往后枚举每颗导弹属于某个上升子序列，还是下降子序列；

  • 如果属于上升子序列，则枚举属于哪个上升子序列（包括新开一个上升子序列）；如果属于下降子序列，可以类似处理。

Solution

迭代加深
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;
const int N = 55;
int h[N], up[N], down[N];
int n;
bool dfs(int depth, int u, int su, int sd) {
    // 如果上升序列个数 + 下降序列个数 > 总个数上限（即深度），则回溯
    if (su + sd > depth) return false; 
    
    //成功搜索到答案，回溯
    if (u == n) return true;
    
    int l = 0, r = su;
    while (l < r) {
        int mid = l + r >> 1;
        if (up[mid] < h[u]) r = mid;
        else l = mid + 1;
    }
    int t = up[r];
    if (r == su) {
        up[r] = h[u];
        if (dfs(depth, u + 1, su + 1, sd)) return true; 
    } else {
        up[r] = h[u];
        if (dfs(depth, u + 1, su, sd)) return true;
        
    }
    up[r] = t;
    
    l = 0, r = sd;
    while (l < r) {
        int mid = l + r >> 1;
        if (down[mid] > h[u]) r = mid;
        else l = mid + 1;
    }
    t = down[r];
    if (r == sd) {
        down[r] = h[u];
        if (dfs(depth, u + 1, su, sd + 1)) return true;
    } else {
        
        down[r] = h[u];
        if (dfs(depth, u + 1, su, sd)) return true;
        down[r] = t;
    }
    
    return false;
}
int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> h[i];
        int depth = 0;//这里的深度是总导弹系统套数，即上升导弹系统 + 下降导弹系统
        while (dfs(depth, 0, 0, 0) == false) ++depth; //迭代加深搜索
        cout << depth << endl;
    }
}
最优性剪枝：维护全局最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int h[N], lastu[N], lastd[N];
int ans;
void dfs(int u, int su, int sd) {
    //如果已经超过了最优解答案，那么直接剪枝
    if (su + sd >= ans) return;
    //没有超过最优解答案，且把所有导弹都考虑到了，即找到最优解
    if (u == n) {
        ans = su + sd;
        return;
    }
    
    int p = upper_bound(lastu, lastu + su, h[u], greater<int>()) - lastu;
    int t = lastu[p];
    if (p == su) {
        lastu[su] = h[u];
        dfs(u + 1, su + 1, sd);
    }
    else {
        lastu[p] = h[u];
        dfs(u + 1, su, sd);
    }
    lastu[p] = t;
    
    p = upper_bound(lastd, lastd + sd, h[u]) - lastd;
    t = lastd[p];
    if (p == sd) {
        lastd[sd] = h[u];
        dfs(u + 1, su, sd + 1);
    } else {
        lastd[p] = h[u]; 
        dfs(u + 1,su ,sd);
        
    }
    lastd[p] = t;
}
int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> h[i];
        ans = n;
        dfs(0, 0, 0);
        cout << ans << endl;
    }
}

897. 最长公共子序列

题目描述

给定两个长度分别为 NN 和 MM 的字符串 AA 和 BB，求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含一个长度为 NN 的字符串，表示字符串 AA。

第三行包含一个长度为 MM 的字符串，表示字符串 BB。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤10001 \le N,M \le 1000

输入样例：

1
2
3
4 5
acbd
abedc

输出样例：

1
3

算法分析

image-20211109164104580

问题分析.PNG

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
using namespace std;
const int N = 1010;
int f[N][N];
char a[N], b[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i];
    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]);
        }
    }
    cout << f[n][m];
}

272. 最长公共上升子序列

题目描述

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 AA 和 BB，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 AA 和 BB 的长度均不超过 30003000。

输入格式

第一行包含一个整数 NN，表示数列 A，BA，B 的长度。

第二行包含 NN 个整数，表示数列 AA。

第三行包含 NN 个整数，表示数列 BB。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围

1≤N≤30001 \le N \le 3000,序列中的数字均不超过 231−12^{31}-1。

输入样例：

1
2
3
4
2 2 1 3
2 1 2 3

输出样例：

1
2

算法分析

LCSLCS

f[i][j]=f[i−1][j−1]+1  (i,j>0,a[i]=b[j])f[i][j]=f[i-1][j-1]+1\;(i,j>0,a[i]=b[j])

f[i][j]=max(f[i][j−1],f[i−1][j])  (i,j>0,a[i]≠b[j])f[i][j]=max(f[i][j-1],f[i-1][j])\;(i,j>0,a[i]\not=b[j])

其中，f[i][j]为a序列前i个元素与b序列前j个元素的LCSLCS长度

LISLIS

f[i]=max f[j]+1 (j<i,a[j]<a[i])f[i]=max~f[j]+1~(j<i,a[j]<a[i])

f[i]为以第i个元素结尾的LISLIS长度。

这道题目是 LIS 与 LCS 的综合。请读者回顾在木节开头部分列举的 LIS 与 LCS 问题的动态规划状态表示，把二者相结合，容易想到以下解法:

F[i,j]F[i, j] 表示 A1∼AiA_{1} \sim A_{i} 与 B1∼BjB_{1} \sim B_{j} 可以构成的以 BjB_{j} 为结尾的 LCIS 的长度。

  • 当 Ai≠BjA_{i} \neq B_{j} 时，有 F[i,j]=F[i−1,j]F[i, j]=F[i-1, j]
  • 当 Ai=BjA_{i}=B_{j} 时，有

F[i,j]=max⁡1≤k<j,Bk<Bj{F[i−1,k]}+1=max⁡1≤k<j,Bk<Ai{F[i−1,k]}+1F[i, j]=\max _{1 \leq k<j, B_{k}<B_{j}}\{F[i-1, k]\}+1=\max _{1 \leq k<j, B_{k}<A_{i}}\{F[i-1, k]\}+1

显然，上面的状态转移方程可以直接用三重循环的程序计算（初始化部分省略）。

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i] == b[j]) {
            f[i][j] = 1;
            for (int k = 1; k < j; k++)
                if (b[k] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
        } else {
            f[i][j] = f[i - 1][j];
        }

在转移过程中，我们把满足 1≤k<j,Bk<Ai1 \leq k<j, B_{k}<A_{i} 的 kk 构成的集合称为 F[i,j]F[i, j] 进行状态转移时的决策集合，记为 S(i,j)S(i, j) 。注意到，在第二层循环 jj 从 1 增加到 mm 时，第一层循环 ii 是一个定值，这使得条件 Bk<AiB_{k}<A_{i} 是固定的。因此，当变量 jj 增加 1 时，kk 的取值范围从 1≤k<j1 \leq k<j 变为 0≤k<j+10 \leq k<j+1，即整数 jj 可能会进入新的决策集合。也就是说，我们只需要 O(1)O(1) 地检查条件 Bj<AiB_{j}<A_{i} 是否满足，已经在决策集合中 的数则一定不会被去除:

S(i,j+1)={S(i,j)Bj≥AiS(i,j)∪{j}Bj<AiS(i, j+1)=\left\{\begin{array}{cc} S(i, j) & B_{j} \geq A_{i} \\ S(i, j) \cup\{j\} & B_{j}<A_{i} \end{array}\right.

所以上面的状态转移方程只需要两重循环即可求解。最终的目标是 max⁡1≤j≤mF[n,j]\max _{1 \leq j \leq m} F[n, j] 。

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i++) {
    // val是决策集合S(i,j)中f[i-1][k]的最大值
    int val = 0;
    for (int j = 1; j <= m; j++) {
        if (a[i] == b[j]) f[i][j] = val + 1;
        else f[i][j] = f[i - 1][j];
        // j即将增大为j+1，检查j能否进入新的决策集合
        if (b[j] < a[i]) val = max(val, f[i - 1][j]);
    }
}

这道题转移部分的优化告诉我们，在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。对于 “决策集合中的元素只增多不减少” 的情景，就可以像 本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移的复杂度降低一个量级。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N];
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 val = 0;
        for (int j = 1; j <= n; ++j) {
            f[i][j] = a[i] == b[j] ? val + 1 : f[i - 1][j];
            if (b[j] < a[i]) val = max(val, f[i - 1][j]);
        }
    }
    int ans = 0;
    for (int j = 1; j <= n; ++j) ans = max(ans, f[n][j]);
    cout << ans;
}