最长子序列总结

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。

相关文章

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
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...
uva 10131 最长子序列

uva 10131 最长子序列

题意： 给大象的体重和智商，求体重按从大到小，智商从高到低的最长子序列，并输出路径。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect
阅读更多...
二分最大匹配总结

二分最大匹配总结

HDU 2444  黑白染色 ，二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter
阅读更多...
整数Hash散列总结

整数Hash散列总结

方法：    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000
阅读更多...
状态dp总结

状态dp总结

zoj 3631  N 个数中选若干数和（只能选一次）<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2