最长子序列总结

2024-03-04 17:28
文章标签 总结 序列 长子

本文主要是介绍最长子序列总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这是最长上升子序列最基础的例子：
给定一串数字 3 2 4 5 1 那么他的最长上升子序列就是 3 4 5
其衍生问题为：

  • 求最长递减子序列、求正方向反方向最长递增/递减子序列
  • 求先上升后下降的最长子序列、
  • 求能完全覆盖整个序列的最小下降子序列个数
  • 求能完全覆盖整个序列的最小上升和下降子序列的和
  • 求最长上升子序列的和

LIS (最长上升子序列，Longest Increasing Subsequence)
LCS (最长公共子序列，Longest Common Subsequence)
LCIS (最长公共上升子序列，Longest Common Increasing Subsequence)

1. 求向左向右最长下降子序列长度
AcWing 1017. 怪盗基德的滑翔翼

给定一个数组，求向左或向右的最长下降子序列

输入格式

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

输出格式

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

数据范围

1≤K≤100,
1≤N≤100,
0

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int a[N], f[N];
int main()
{int K;cin >> K;while(K--){cin >> n;for(int i = 1;i <=n; i++) cin >> a[i];int res = 0;//背两段正反上升子序列模版//正向求解LIS问题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);res = max(res, f[i]);}//反向求解LIS问题for(int i = n; i >=1 ; i --){f[i] = 1;for(int j = n; j > i ; j --)if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);res = max(res, f[i]);  }cout << res << endl;}return 0;
}
2. 求先上升后下降的最长子序列
AcWing 1014. 登山

登山是先上山后下山求最大经过点数
可以思考为从peak分割，求左最长上升+右最长下降

输入格式

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

输出格式

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

数据范围
2≤N≤1000
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4

//先上升后下降，所以对于peak a[k]，向左向右各求最长下降子序列，也可以理解成反向上升
//所以就是a[1]到a[k-1]的最长上升子序列和a[n]到a[k-1]的最长上升子序列之和
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N], g[N];
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);}int res = 0;for(int i = 1; i <= n; i++)res = max(res, f[i] + g[i]-1);//要记得-1，peak是重合的cout << res;return 0;}
AcWing 482. 合唱队行

给定一群人的身高，按中间高两边低站队，问多少人出列才能让剩下的人排成合法队形
意思就是问 挑出几个人才能满足合唱队列，和爬山一样的，只不过是输出剩下的

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int f[N], g[N], a[N];
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);}int res = 0;for(int i = 1;i <=n; i++) res = max(res, f[i]+g[i]-1);cout << n-res; //就这里不同return 0;}
3. 实际问题抽象为最长上升子序列问题
AAcWing 1012. 友好城市

一条河南北两边有友好城市对
求航线不交叉的最大值
其实想一下，不交叉就是一侧排序，求另一侧上升子序列最大数

输入格式

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

输出格式

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

数据范围
1≤N≤5000,
0≤Xi≤10000
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4

//按一遍的城市排序，求另一边的最长上升子序列就是答案
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n;
int f[N];
typedef pair PII;
PII q[N];
int main()
{cin >> n;for(int i = 0; i < n; i++) scanf("%d%d", &q[i].first, &q[i].second);sort(q, q + n);for(int i = 0; i < n; i ++){f[i] = 1;for(int j = 0; j < i;j ++)if(q[i].second > q[j].second) f[i] = max(f[i], f[j] + 1);}int res = 0;for(int i=0; i < n;i ++ ) res= max(res, f[i]);cout << res;return 0;}
4. 最大上升子序列之和
AcWing 1016. 最大上升子序列和

比较简单，就是把求数量问题改为求和问题
把最长上升子序列的状态更新的+1改为+a[i]即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;int n;
int q[N];
int f[N], g[N];int main()
{//第一题最长递减子序列模版while(cin >> q[n]) n ++;int res = 0;for(int i = 0; i < n; i ++ ){f[i] = 1;for(int j = 0; j < i;j ++ ){if(q[i] <= q[j]) f[i] = max(f[i],f[j] + 1);}res = max(res, f[i]);}cout << res << endl;//g存所有子序列末尾，cnt来存当前子序列的个数int cnt = 0;for(int i = 0; i < n; i ++){int k = 0; //k是标号, 遍历所有序列//没有遍历完所有序列 && k序列的结尾小于当前数 那么k++，到下一个序列while (k < cnt && g[k] < q[i]) k ++ ;g[k] = q[i];    //这样的存法会让g中递增排序，因此需更新g[k]if (k >= cnt) //说明没有序列大于等于当前数，那么开一个新的序列{cnt++;}}cout << cnt << endl;return 0;
}
6.求能完全覆盖整个序列的最小上升和下降子序列的和

用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹
dfs(u,su,sd)意味着已有su个上升，sd个下降，正在处理第u个数
剩下的就是上一个题加深搜模版了，要注意恢复现场，分类讨论dfs的下一层情况

下面解释下存最长上升/下降子序列末尾的数组up[k], down[k]的原理：
例子：3， 2， 4， 3，求down
第一轮为[[3]]，第二轮为[[3,2]]，第三轮为[[3,2],[4]]，第四轮为[[3,2],[4,3]]。因此down为[2,3]
所以down的机制里永远是递增的末尾。up同理

AcWing 187. 导弹防御系统

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

输入格式

输入包含多组测试用例。
对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。
第二行包含 n 个不同的整数，表示每个导弹的高度。

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

输出格式
数据范围
1≤n≤50
输入样例：
5
3 5 2 4 1
0
输出样例：
2

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n;
int q[N];
int ans;
//up[k]和down[k]数组存第k套(上升/下降)数组的最后一个子序列
int up[N], down[N];
//dfs(u,su,sd)意味着已有su个上升，sd个下降，正在处理第u个数
//dfs(第几颗导弹，最长上升子序列个数，最长下降子序列个数)
void dfs(int u, int su, int sd)
{//由于是深搜，为了筛去答案更差的结果，所以更差的就直接return不用算了if(su + sd >= ans) return;if(u == n){//如果说u==n那么就找到了一种匹配的方法ans = su + sd;return;}//情况1：将当前数放到上升子序列中int k = 0;//用来遍历已存在的子序列尾while(k < su && up[k]>q[u]) k++;int temp = up[k];//临时备份up[k]up[k] = q[u]; //用当前数更新第k个上升子序列的末尾if(k < su) dfs(u + 1, su,sd);//k=su代表新开了一个数组up[k] = temp;//恢复现场//情况1：将当前数放到下降子序列中k = 0;while(k < sd && down[k]> n, n){for(int i=0; i < n; i ++) cin >> q[i];ans = n;//更新ans来维护最小防御系统套数dfs(0,0,0);cout << ans << endl;}return 0;
}
7. 最长公共上升子序列

状态表示：

  • f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合
  • f[i][j]的值等于该集合的子序列中长度的最大值

状态计算（对应集合划分）：
首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集：

  • 不包含a[i]的子集，最大值是f[i - 1][j]
  • 包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：
    • 子序列只包含b[j]一个数，长度是1
    • 子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1(倒数第一个数b[j])
    • …
    • 子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1

如果直接按上述思路实现，需要三重循环，对应未优化的朴素算法

然后我们发现每次循环求得的maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。
因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。

最终答案枚举子序列结尾取最大值即可。

AcWing 272. 最长公共上升子序列
输入格式

第一行包含一个整数 N，表示数列 A，B 的长度。
第二行包含 N 个整数，表示数列 A。第三行包含 N 个整数，表示数列 B。

输出格式

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

数据范围
1≤N≤3000 ,序列中的数字均不超过 2^31−1。
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
朴素做法，未优化，会超时：
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n;
int a[N],b[N],f[N][N];
int main()
{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 ++){//先给把b序列中的新值添加过来，直接继承即可f[i][j] = f[i-1][j];//按这样的状态表示方法，f[i][j-1]不一定存在if(a[i]==b[j])//只有在新添的结尾字符相同时才存在{f[i][j] = max(f[i][j], 1);//答案至少为1，且要是公共的，所以只能写在这里//把b[j]前的所有a遍历一遍,判断上升for(int k = 1;k < j; k++)if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k] + 1);}}int res = 0;//枚举最大时候让a全选，然后枚举max的bfor(int i = 1; i <= n; i ++) res = max(res, f[n][i]);cout << res;return 0;
}
优化就是对代码做等价变形
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n;
int a[N],b[N],f[N][N];
int main()
{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 ++){f[i][j] = f[i-1][j];if(a[i] ==b[j]) f[i][j] = max(f[i][j], maxv);if(b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);}}int res = 0;for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);cout << res;return 0;
}

这篇关于最长子序列总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/773897。

相关文章

最长公共子序列问题的深度分析与Java实现方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列（LCS）问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动
阅读更多...
关于最长递增子序列问题概述

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法：贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列，例如 nums = [10, 9, 2
阅读更多...
Python中连接不同数据库的方法总结

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo
阅读更多...
Git提交代码详细流程及问题总结

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》：本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push
阅读更多...
Kubernetes常用命令大全近期总结

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes（有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes？Kubernetes常用命令总
阅读更多...
Python中实现进度条的多种方法总结

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres
阅读更多...
Android数据库Room的实际使用过程总结

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象（DAO）和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类（Entity）3.创建数据访问对象（DAO
阅读更多...
Java向kettle8.0传递参数的方式总结

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的
阅读更多...
C# Task Cancellation使用总结

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2