动态规划专题刷题记录②：最长上升子序列

Here_SDUT

发布于 2022-06-29 15:21:50

9910

发布于 2022-06-29 15:21:50

一、最长上升子序列模型

最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。解决最长递增子序列问题的算法最低要求O(n log n)的时间复杂度。(摘自维基百科)

分析方法：

二、例题

题谱:

895. 最长上升子序列

1.题面

题目链接

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

输入格式 第一行包含整数N。

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

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

数据范围 1≤N≤1000， −109≤数列中的数≤109 输入样例：

7
3 1 2 1 8 5 6

输出样例：

2.题目分析

朴素的LIS做法，这里展示O(n^2)的做法，思考方法见上方最长上升子序列模型的思考方法。

3.代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+10;

int a[maxn], dp[maxn];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = 0; j <= i-1; j++) {
            if(a[j] < a[i])
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int res = -1;
    for(int i = 0; i < n; i++) res = max(res, dp[i]);
    cout << res << endl;
}

896. 最长上升子序列 II

1.题面

题目链接

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

输入格式 第一行包含整数N。

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

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

数据范围 1≤N≤100000， −10^9≤数列中的数≤10^9 输入样例：

7
3 1 2 1 8 5 6

输出样例：

2.题目分析

这题1e5级别不能用O(n^2)来处理了，需要优化成O(nlogn)。具体方法：用一个数组q[len]来存长度为len的最长上升子序列的最后一个数字的最小值，利用反证法可以证明得到：q[]中存的数字是随下标增加而严格递增的，即具有单调性（假设q[2] 小于等于 q[3],则q[3]代表的序列的前两个数字组成长度为2的子序列的末尾数字小于q[2]，与q存的最小值的定义矛盾）。既然具有单调性，可以从第一个数字开始插入每个数字，每次插入用二分查找末尾数字比待插入数字小的最长的子序列，插完所有数字，q下标达到的最大值就是最长上升子序列的长度

3.代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int a[maxn], q[maxn];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    for(int i = 0; i <= n; i++) q[i] = i;//初始化，保证q[i]的单调性
    int len = 0;//表示当前时刻所有子序列的最长长度
    for(int i = 0; i < n; i++) {
        int l = 0, r = len;
        while(l < r) {
            int mid = l + r + 1 >> 1;//由于l = mid 故需要 l+r+1
            if(q[mid] < a[i]) l = mid;//向右找，同时mid也可能为答案，不能舍去
            else r = mid - 1;
        }
        q[r+1] = a[i];//r是插入的位置，插入后长度+1，故直接更新r+1的值
        len = max(len, r+1);//同上
    }
    cout << len << endl;
}

1017. 怪盗基德的滑翔翼

1.题面

题目链接

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

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

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

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

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

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

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

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

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

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

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

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

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

数据范围 1≤K≤100, 1≤N≤100, 0<h<10000

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

输出样例：

6
6
9

2.题目分析

此题要求选择任意一个方向使得跳跃楼房最多，且每次跳跃的楼房都要比之前的小，可以想到LIS问题，只需分别向左和向右求一次LIS就行了

3. 代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

int a[maxn], dp[maxn];

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) cin >> a[i];
        int res = -1;
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            for(int j = 0; j <= i-1; j++) {
                if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        for(int i = 0; i < n; i++) res = max(res, dp[i]);
        for(int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            for(int j = n - 1; j >= i + 1; j--) {
                if(a[] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        for(int i = 0; i < n; i++) res = max(res, dp[i]);
        cout << res << endl;
    }
}

1014. 登山

1. 题面

题目链接

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

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

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

输入格式 第一行包含整数N，表示景点数量。

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

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

数据范围 2≤N≤1000 输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

2.题面分析

要求先向上走再向下走，求最多能走多少景点，可以考虑分别向左和向右求一次LIS，其中向左求LIS相当于向右求最长递减的子序列，所以遍历每个点，找到向左LIS加上向右LIS的最大值就是答案。

3. 代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1100;

int a[maxn], dp1[maxn], dp2[maxn];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int res = -1;
    for(int i = 0; i < n; i++) {
        dp1[i] = 1;
        for(int j = 0; j <= i-1; j++) {
            if(a[j] < a[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }
    for(int i = n - 1; i >= 0; i--) {
        dp2[i] = 1;
        for(int j = n - 1; j >= i + 1; j--) {
            if(a[j] < a[i]) dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }
    for(int i = 0; i < n; i++) res = max(res, dp1[i]+dp2[i] - 1);
    cout << res << endl;
}

482. 合唱队形

1. 题面

题目链接

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

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T_1，T_2，…，T_K , 则他们的身高满足 T_1 <…< T_i > T_i + 1 >… >T_K(1≤i≤K)

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

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

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

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

数据范围 2≤N≤100, 130≤T_i≤230 输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

2.题目分析

问最少出列几个人可以使得队伍变成先上升后下降的队形，做法和上一题一样，求出最大值用总人数减去即可。

3.代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1100;

int a[maxn], dp1[maxn], dp2[maxn];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int res = -1;
    for(int i = 0; i < n; i++) {
        dp1[i] = 1;
        for(int j = 0; j <= i-1; j++) {
            if(a[j] < a[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }
    for(int i = n - 1; i >= 0; i--) {
        dp2[i] = 1;
        for(int j = n - 1; j >= i + 1; j--) {
            if(a[j] < a[i]) dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }
    for(int i = 0; i < n; i++) res = max(res, dp1[i]+dp2[i] - 1);
    cout << n - res << endl;
}

1012. 友好城市

1. 题面

题目链接

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

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

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

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

输入格式 第1行，一个整数N，表示城市数。

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

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

数据范围 1≤N≤5000, 0≤x_i≤10000 输入样例：

输出样例：

2.题目分析

题目有两个要求：1.每个城市建一座桥。2.所有桥之间不能相交。我们将城市画出，友好城市之间连线，类似下图：

将南岸城市设为自变量，北岸为应变量，按照自变量排好序，则应变量会是一个不一定有序的序列，我们可以得到下面结论：

1.对于每一种合法的建桥方式：对应选择的应变量必然是一个上升序列。

2.对于应变量的一个上升子序列：必然对应着一个合法的建桥方法。

证明可以通过画图找反例得出。

因此，寻找最多的一种建桥方式就是找应变量的LIS，代码实现就相当轻松了，将一条边的两端点存入一个pair数组，sort按照first排序后求second的LIS即可。

3.代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+10;

typedef pair<int,int> PII;

int dp[maxn];
PII a[maxn];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a, a+n);
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++) {
            if(a[j].second < a[i].second) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int res = -1;
    for(int i = 0; i < n; i++) res = max(res, dp[i]);
    cout << res << endl;
}

1016. 最大上升子序列和

1. 题面

题目链接

一个数的序列 bi，当 b_1<b_2<…<b_S

对于给定的一个序列(a_1,a_2,…,a_N)，我们可以得到一些上升的子序列(a_{i1},a_{i2},…,a_{iK})，这里1≤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≤1000 输入样例：

7
1 7 3 5 9 4 8

输出样例：

题目分析

运用“闫氏分析法”，可以画出下图，代码实现就很轻松了。

代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e3+10;

int a[maxn], dp[maxn];

int main() {
    int n;
    cin >> n;
    int res = -1;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) {
        dp[i] = a[i];
        for(int j = 0; j < i; j++) {
            if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + a[i]);
        }
        res = max(res, dp[i]);
    }
    cout << res << endl;
}

1010. 拦截导弹

1.题面

题目链接

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

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

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

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

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

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

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

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

数据范围 雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

2. 题目分析

题目有两问：1.求一个导弹系统最多拦截多少导弹。2.需要几套导弹系统第一问就是求一下LIS很好解决，主要看第二问。

利用贪心的思想，对于每颗高度为h的导弹有两种处理方式：1.找到现存导弹系统中高度大于h的最小的导弹系统，用它拦截。2.用一个新的导弹系统拦截。代码实现也很简单，类比问题896（优化的LIS问题），用g[]来记录每个导弹系统的当前可拦截高度，并且易得g[]的值是随下标递增的，故可以循环一遍查找。

这里用调整法证明一下为何贪心的方式就是最优解：假设A表示贪心法求得的导弹系统序列，B表示最优解。若A和B在某位置i出不同，由于序列是单调递增的，故A[i]<B[i]>B[i-1]（A贪心法保证下标相同时存的值一定最小），那么可以交换A[i]和B[i],并保证A和B序列的合法性，故每次遇到不同的位置就进行交换，最终可以使得A=B，即最优解就是贪心解。

3. 代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

int a[maxn], dp[maxn], g[maxn];

int main () {
    int n = 0;
    while(cin >> a[n]) n++;
    int res = 0;
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++) {
            if(a[j] >= a[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res, dp[i]);
    }
    cout << res << endl;
    int cnt = 0;
    for(int i = 0; i < n; i ++) {
        int k = 0;
        while(k < cnt && g[k] < a[i]) k++;
        g[k] = a[i];
        if(k >= cnt) cnt++;
    }
    cout << cnt << endl;
}

187. 导弹防御系统

1.题面

题目链接

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

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

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

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

输入格式 输入包含多组测试用例。

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

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

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

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

数据范围 1≤n≤50 输入样例：

5
3 5 2 4 1
0

输出样例：

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

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

2. 题目分析

此题和上一题的区别就是导弹系统可以是递增也可以是递减的，由于数据很小，可以在上一题的基础上进行dfs暴力搜索，用两个数组分别记录上升导弹系统和下降导弹系统的当前可拦截高度。具体实现看代码。

3. 代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 60;

int a[maxn], down[maxn], up[maxn];
int ans, n;

void dfs(int now, int d, int u) {
    if(d + u >= ans) return;
    if(n == now) {ans = d + u;return;}
    int k = 0;
    while(k < d && down[k] <= a[now]) k++;
    int temp = down[k];
    down[k] = a[now];
    if(k >= d) dfs(now+1, d+1,u);
    else dfs(now+1, d, u);
    down[k] = temp;

    k = 0;
    while(k < u && up[k] >= a[now]) k++;
    temp = up[k];
    up[k] = a[now];
    if(k >= u) dfs(now+1, d,u+1);
    else dfs(now+1, d, u);
    up[k] = temp;
}

int main() {
    while(cin >> n && n) {
        for(int i = 0; i <n ;i++) cin >> a[i];
        ans = n;
        dfs(0,0,0);
        cout << ans << endl;
    } 
}

272. 最长公共上升子序列

1. 题面

题目链接

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

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

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

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

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

数列A和B的长度均不超过3000。

输入格式 第一行包含一个整数N，表示数列A，B的长度。

第二行包含N个整数，表示数列A。

第三行包含N个整数，表示数列B。

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

数据范围 1≤N≤3000,序列中的数字均不超过2^{31}−1 输入样例：

4
2 2 1 3
2 1 2 3

输出样例：

2. 题目分析

此题就是最长上升子序列和最长公共子序列的结合。

可以看出，状态可以分为包含a[i]和不包含a[i]两种，不包含a[i]的状态可以用f[i-1,j]表示。包含a[i]的状态可以继续按照倒数第二个数字是什么来细分为多个情况，并且可以分别表示出来。

3. 代码

暴力实现的代码，思路正确TLE还需优化：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3100;

int a[maxn], b[maxn], dp[maxn][maxn];

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[i][j] = dp[i-1][j];
            if(a[i] == b[j]){
                dp[i][j] = max(dp[i][j], 1);
                for(int k = 1; k < j; k++) {
                if(b[k] < b[j]) dp[i][j] = max(dp[i][j], dp[i][k] + 1);
                }
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, dp[n][i]);
    cout << res << endl;
}

4. 优化

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3100;

int a[maxn], b[maxn], dp[maxn][maxn];

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 maxv = 1;
        for(int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j];
            if(b[j] == a[i]) dp[i][j] = max(dp[i][j], maxv);
            if(b[j] < a[i]) maxv = max(maxv, dp[i][j] + 1);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, dp[n][i]);
    cout << res << endl;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-1-10 1，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度