葫芦岛做网站价格,网络科技公司注册资金,需要企业网站开发,门户营销型网站搭建一.最长上升子序列#xff08;LIS#xff09;的相关知识
1.最长上升子序列#xff08;Longest Increasing Subsequence#xff09;#xff0c;简称LIS#xff0c;也有些情况求的是最长非降序子序列#xff0c;二者区别就是序列中是否可以有相等的数。假设我们有一个序…一.最长上升子序列LIS的相关知识
1.最长上升子序列Longest Increasing Subsequence简称LIS也有些情况求的是最长非降序子序列二者区别就是序列中是否可以有相等的数。假设我们有一个序列 b i当b1 b2 … bS的时候我们称这个序列是上升的。
或许我们刚开始对于这样的名词感到陌生对于解释也不理解那我们就要知道它的前置知识 一.什么是子序列 一个序列A{a1,a2,...an}中任意删除若干项剩余的序列叫做A的一个子序列。例如序列A{1,3,5,4,2}删除其中的第3项和第5项得到序列B{1,3,4}删除其中的第3项和第4项得到序列C{132}此时序列B和C是序列A的子序列。 二.什么是最长子序列 如果序列中的元素是从小到大排列的则该序列为上升序列如果该序列又是其它序列的子序列则称为上升子序列。例如“1.1 子序列”中提到的B是A的上升子序列而C是A的子序列但不是上升子序列。 了解这两个前置知识那么最长上升子序列就很容易理解了。
即包含元素最多的上升子序列叫做最长上升子序列。 二.LIS长度的求解方法
一.方法一动态规划O(n^2)朴素法
动态规划的一个特点就是当前解可以由上一个阶段的解推出 由此把我们要求的问题简化成一个更小的子问题。我们求最长上升子序列也符合这一特点我们要求前n个数的最长上升子序列就是可以转换成求前n-1个数的最长上升子序列......这样逐步分解直到求前1个数的最长上升子序列。 状态转移方程为dp[i]max(dp[i],dp[j]1)
其核心代码段为
for (int i 1; i n; i) {for (int j 1; j i; j) {if (a[i] a[j])dp[i] max(dp[i], dp[j] 1);}}for (int i 1; i n; i) {ans max(ans, dp[i]);} 二.方法二贪心二分O(nlogn)
用一个low数组记录长度low[i]表示长度都为i的LIS结尾元素的最小值这样我们在记录low的时候当a[i]大于low[当前LIS最大长度]时候直接将a[i]接在low中否则在low中二分查找大于等于当前元素a[i]的第一个位置pos用a[i]替换掉之前的low[pos].最后我们找一下最长上升子序列下标满足的解记录下该子序列即可.(注意low数组不一定是最长上升子序列只是长度对等)
这里的二分操作可以用STL中的lower_bound函数实现。
核心代码段
low[sum]a[1];
for (int i 2; i n; i) {if (a[i] low[sum])low[sum] a[i];else{int k lower_bound(low 1, low sum 1, a[i]) - dp;low[k] a[i];}
} 三.例题分析 一.B3637 最长上升子序列 这一题就相当于最长上升子序列的模版题通过动态规划朴素法就可以解决这里可以当做模版学习。
#includebits/stdc.h
using namespace std;
#define N 1000005
int dp[N], a[N];
int ans, n, m, sum;
int main()
{cin n;for (int i 1; i n; i) {cin a[i];dp[i] 1; //初始化dp都为1即自身是一个上升子序列}for (int i 1; i n; i) {for (int j 1; j i; j) { //如果在之前的序列有小于a[i]的更新dpif (a[i] a[j])dp[i] max(dp[i], dp[j] 1);}}for (int i 1; i n; i) {ans max(ans, dp[i]); //找出最长的上升子序列}cout ans endl;return 0;
} 二.LIS 这一题和刚刚的题目的意思是一模一样的唯一的区别就是数据范围变大了变为1e5如果我们还是和刚刚一样使用O(n^2)的方法肯定会超时那么我们就应该使用方法二贪心二分 Onlogn #includebits/stdc.h
using namespace std;
#define N 100005
int a[N], b[N];
int n, m, sum, ans;
int main()
{cin n;for (int i 1; i n; i) {cin a[i];}b[sum] a[1]; //核心代码段没什么好说的for (int i 2; i n; i) {if (a[i] b[sum])b[sum] a[i];else{int k lower_bound(b 1, b sum 1, a[i]) - b;b[k] a[i];}}cout sum endl;return 0;
} 这里给大家留下两道练习题这两道题都是在此基础上的变形题可以会有点难都是洛谷上的题可以看题解后面我也会给出分析。
[ARC149B] Two LIS Sum
P8736 [蓝桥杯 2020 国 B] 游园安排 另外关于LIS还有一个姊妹叫作LCS最长公共上上子序列下次我们将讲解相关内容好了今天的内容就到这里了。~QVQ~
