首页 > 其他分享 >最长XX子序列

最长XX子序列

时间：2023-08-02 17:47:10浏览次数：39  
标签：int 1005 元素 XX 序列 INF 最长

@

目录

1 最长上升子序列

最长上升子序列（LIS, the Longest Increasing Subsequence），指对于一个数列，一个最长的子序列满足 \(a_i < a_j (i < j)\) （即严格递增）。该子序列被称为最长上升子序列。

例： 5 7 1 9 2 4 3 7 6 中最长子序列的长度是 4，最长上升子序列为 1 2 4 7、1 2 4 6、1 2 3 7和1 2 3 6。

1.1 求最长上升子序列的长度-分治解

首先构造分治式：

考虑以 \(i\) 结尾的最长上升子序列，发现其长度只与上一个元素 \(j\) 有关，只要满足 \(a_j < a_i\)，便可以构造出一个以 \(a_i\) 结尾、 \(a_j\) 为倒数第二个元素的上升子序列。显然，其长度为以 \(a_j\) 结尾的最长上升子序列长度加一。

  • 原问题：求以 \(a_i\) 结尾的最长上升子序列的长度。

  • 子问题：求以 \(a_j\) 结尾的最长上升子序列的长度。（其中 \(a_j < a_i , j < i\)）。

  • 基本情况：无（因为最长上升子序列的第一个元素必然没有比他更小的元素，若有则不构成最长上升子序列）

  • 合并：\(\max \{\) 子问题的解 \(\}+1\)

分析时间复杂度：由于重复计算，最坏情况下可能达到 \(O(2^n)\)。进行记忆化搜索，时间复杂度降为 \(O(n^2)\)

当然，有了记忆化，也可以逆推出其中一条最长上升子序列。时间复杂度 \(O(n)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;

int a[1005],f[1005];
int solve(int i) { // 以 i 为最后一个元素的最长上升子序列长度
	if(f[i]!=0) return f[i];// 这个答案已经被搜索过
	f[i]=1;// 初值为一（只有该元素）
	for(int j=1;j<i;j++)// 子问题
		if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);// 递归分治
	return f[i];
}
void LIS(int i) { // 以 i 结尾的最长上升子序列
	for(int j=1;j<i;j++)
		if(a[j]<a[i]&&f[j]+1==f[i]) {
			LIS(j);// 输出一条最长上升子序列即可
			break;
		}
	cout<<a[i]<<" ";
	return ;
}

int main() {
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
		if(solve(i)>f[ans]) ans=i;
	cout<<f[ans]<<endl;// 最长上升子序列长度
	LIS(ans);
	return 0;
}

1.2 最长上升子序列-DP解

根据分治解设计动态规划。

  • 状态：\(dp_i\) 表示以 \(a_i\) 结尾的最长上升子序列长度。

  • 转移：\(dp_i=\max \{dp_i,dp_j+1|a_j<a_i,j<i\}\)

  • 初值：\(dp_i=1 (1 \leq i \leq n)\)

  • 目标：\(\max\{dp_i\} (1 \leq i \leq n)\)

时间复杂度 \(O(n^2)\)

代码（只放关键部分）：

for(int i=1;i<=n;i++) {
	dp[i]=1;
	for(int j=1;j<i;j++)
		if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
	ans=max(ans,dp[i]);
}

1.3 最长上升子序列-贪心解

优化前，先举个栗子看看：

2 7 3 9 4 6 10 1 4 其中最长上升子序列为 2 3 4 6 10。

根据 DP 模拟一下：

a[]    2  7  3  9  4  6 10  1  4
dp[]   1  2  2  3  3  4  5  1  3
观察：    ^  ^

我们发现：当以 3 结尾的LIS长度变成 2 时，相比较 7 ，显然是 3 更优一些，因为更小的元素意味着后面可以接更多的值。如 \(a_5=4\) ，它只能接在 3 后面，而不能接在 7 后面。

我们可以见一个 \(b\) 数组，来存储这些信息。我们令 \(b_i\) 表示长度为 \(i\) 的上升子序列的结尾的最小值。由于要让值尽量的小，我们设 \(b\) 的初值为 INF （无穷大）。我们进行如下模拟：

\(a_1=2\) ，发现 \(b\) 皆为 INF ，于是 \(a_1\) 变为上升子序列的第一个元素，即 \(b_1=1\)。这时 \(b\) 为：2 INF INF INF INF...

\(a_2=7\) ，发现它比 \(b_1\) 即第一个元素大，可以作为第二个元素，即 \(b_2=7\)。这时 \(b\) 为：2 7 INF INF INF INF...

\(a_3=3\) ，根据刚才的结论，由于 3 比 7 小，无法做为第三个元素，而 3 相较 7 更优，替换 7 ，即 \(b_2=3\)。这时 \(b\) 为：2 3 INF INF INF INF...

\(a_4=9\) ，由于它比 \(b_2\) 即最后一个元素大，所以把它作为一个新的元素，即 \(b_3=9\)。这时 \(b\) 为：2 3 9 INF INF INF INF...

\(a_5=4\) ，由于不能作为下一个元素，所以我们寻找它可以替换的元素。我们最小只能把 \(b_3=9\) 替换，即 \(b_3=4\)。这时 \(b\) 为：2 3 4 INF INF INF INF...

\(\cdots \cdot \cdots\)

我们发现：\(b\) 无论如何变化，始终保持单调递增

这样，我们便可以得到如下操作：

  1. 初始化 \(b\) 为 INF，\(cnt\) 设为 0 （表示目前最长上升子序列的最长长度，也是 \(b\) 中最后一个不为 INF 的位置）

  2. 得到一个 \(a_i\) ，若它比 \(b_{cnt}\) 大，则把它作为新的元素，\(cnt \leftarrow cnt+1 , b_{cnt} \leftarrow a_i\) 。否则二分查找第一个大于等于该值的元素 \(b_j\) ，替换 \(b_j \leftarrow a_i\)

  3. 重复执行操作 2

这样，最终 \(cnt\) 便是最长上升子序列的长度。不过要注意了，\(b\) 数组不一定是最长上升子序列。

二分查找时间复杂度 \(O(\log_2(n))\) ，遍历 \(a\) 时间复杂度 \(O(n)\) ，总体时间复杂度 \(O(n\log_2(n))\)

这里还顺便还原了一下最长上升子序列。

其中 \(t_i\) 表示 \(a_i\) 作为最长上升子序列结尾的前驱（上一个元素在 \(t\) 中的坐标）。由于放入 \(b\) 后 \(a\) 数组的坐标可能会乱，所以用 \(r_i\) 来表示 \(b_i\) 在 \(a\) 中的坐标。

在长度增加时，更新皆为元素的前驱；而在替换元素使，也要继承原来元素的前驱。

代码：

#include <bits/stdc++.h>
using namespace std;

int a[1005],b[1005];
int t[1005],r[1005];// 用于还原最长上升子序列
// t[i] 表示 a[i] 作为结尾的最长上升子序列的上一个元素
// r[i] 表示 b[i] 在 a 中的坐标
const int INF=1e9;
void LIS(int i) {
	if(i==0) return ;
	LIS(t[i]);
	cout<<a[i]<<" ";
	return ;
}

int main() {
	int n,cnt=0,ansi=0;
	cin>>n;
	for(int i=1;i<=n;i++) b[i]=INF;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		int p=lower_bound(b+1,b+1+n,a[i])-b;// 这里使用了 C++ 内置的二分查找
		// lower_bound 返回的是第一个大于等于查找元素的值的地址
		if(b[p]==INF) {
			b[++cnt]=a[i];// 作为结尾元素，长度加一
			t[i]=r[cnt-1];// t[i] 指向的是上一个元素
			ansi=i;
		}
		else t[i]=t[r[p]],b[p]=a[i];// a[i] 比 b[p] 更优，替换
		r[p]=i;// b 中第 p 个元素为 i
	}
	cout<<cnt<<endl;// 最长上升子序列长度
	LIS(ansi);// 还原 LIS
	return 0;
}

2 其他最长XX子序列

其实只要稍微修改一下二分查找就行了（有些可能要自己打）。

这里列出了四种最长子序列的贪心（手写 lower_bound ）版本的代码：

2.1 最长严格上升子序列 实现

#include <bits/stdc++.h>
using namespace std;

int a[1005],b[1005];
int t[1005],r[1005];// 用于还原最长上升子序列
// t[i] 表示 a[i] 作为结尾的最长上升子序列的上一个元素
// r[i] 表示 b[i] 在 a 中的坐标
const int INF=1e9;
void LIS(int i) {
	if(i==0) return ;
	LIS(t[i]);
	cout<<a[i]<<" ";
	return ;
}
int LowerBound(int l,int r,int val) {// [l,r]
	while(l<=r) {
		int mid=l+r>>1;
		if(val>b[mid]) l=mid+1;
		else r=mid-1;
	}
	return l;
}

int main() {
	int n,cnt=0,ansi=0;
	cin>>n;
	for(int i=1;i<=n;i++) b[i]=INF;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		int p=LowerBound(1,n,a[i]);
		if(b[p]==INF) {
			b[++cnt]=a[i];// 作为结尾元素，长度加一
			t[i]=r[cnt-1];// t[i] 指向的是上一个元素
			ansi=i;
		}
		else t[i]=t[r[p]],b[p]=a[i];// a[i] 比 b[p] 更优，替换
		r[p]=i;// b 中第 p 个元素为 i
	}
	cout<<cnt<<endl;// 最长上升子序列长度
	LIS(ansi);// 还原 LIS
	return 0;
}

2.2 最长不严格上升子序列 实现

#include <bits/stdc++.h>
using namespace std;

int a[1005],b[1005];
int t[1005],r[1005];// 用于还原最长上升子序列
// t[i] 表示 a[i] 作为结尾的最长上升子序列的上一个元素
// r[i] 表示 b[i] 在 a 中的坐标
const int INF=1e9;
void LIS(int i) {
	if(i==0) return ;
	LIS(t[i]);
	cout<<a[i]<<" ";
	return ;
}
int LowerBound(int l,int r,int val) {// [l,r]
	while(l<=r) {
		int mid=l+r>>1;
		if(val>=b[mid]) l=mid+1;
		else r=mid-1;
	}
	return l;
}

int main() {
	int n,cnt=0,ansi=0;
	cin>>n;
	for(int i=1;i<=n;i++) b[i]=INF;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		int p=LowerBound(1,n,a[i]);
		if(b[p]==INF) {
			b[++cnt]=a[i];// 作为结尾元素，长度加一
			t[i]=r[cnt-1];// t[i] 指向的是上一个元素
			ansi=i;
		}
		else t[i]=t[r[p]],b[p]=a[i];// a[i] 比 b[p] 更优，替换
		r[p]=i;// b 中第 p 个元素为 i
	}
	cout<<cnt<<endl;// 最长上升子序列长度
	LIS(ansi);// 还原 LIS
	return 0;
}

2.3 最长严格下降子序列 实现

#include <bits/stdc++.h>
using namespace std;

int a[1005],b[1005];
int t[1005],r[1005];// 用于还原最长上升子序列
// t[i] 表示 a[i] 作为结尾的最长上升子序列的上一个元素
// r[i] 表示 b[i] 在 a 中的坐标
const int INF=1e9;
void LIS(int i) {
	if(i==0) return ;
	LIS(t[i]);
	cout<<a[i]<<" ";
	return ;
}
int LowerBound(int l,int r,int val) {// [l,r]
	while(l<=r) {
		int mid=l+r>>1;
		if(val<b[mid]) l=mid+1;
		else r=mid-1;
	}
	return l;
}

int main() {
	int n,cnt=0,ansi=0;
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		int p=LowerBound(1,n,a[i]);
		if(b[p]==0) {
			b[++cnt]=a[i];// 作为结尾元素，长度加一
			t[i]=r[cnt-1];// t[i] 指向的是上一个元素
			ansi=i;
		}
		else t[i]=t[r[p]],b[p]=a[i];// a[i] 比 b[p] 更优，替换
		r[p]=i;// b 中第 p 个元素为 i
	}
	cout<<cnt<<endl;// 最长上升子序列长度
	LIS(ansi);// 还原 LIS
	return 0;
}

2.4 最长不严格下降子序列 实现

#include <bits/stdc++.h>
using namespace std;

int a[1005],b[1005];
int t[1005],r[1005];// 用于还原最长上升子序列
// t[i] 表示 a[i] 作为结尾的最长上升子序列的上一个元素
// r[i] 表示 b[i] 在 a 中的坐标
const int INF=1e9;
void LIS(int i) {
	if(i==0) return ;
	LIS(t[i]);
	cout<<a[i]<<" ";
	return ;
}
int LowerBound(int l,int r,int val) {// [l,r]
	while(l<=r) {
		int mid=l+r>>1;
		if(val<=b[mid]) l=mid+1;
		else r=mid-1;
	}
	return l;
}

int main() {
	int n,cnt=0,ansi=0;
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		int p=LowerBound(1,n,a[i]);
		if(b[p]==0) {
			b[++cnt]=a[i];// 作为结尾元素，长度加一
			t[i]=r[cnt-1];// t[i] 指向的是上一个元素
			ansi=i;
		}
		else t[i]=t[r[p]],b[p]=a[i];// a[i] 比 b[p] 更优，替换
		r[p]=i;// b 中第 p 个元素为 i
	}
	cout<<cnt<<endl;// 最长上升子序列长度
	LIS(ansi);// 还原 LIS
	return 0;
}

Last

就讲到这里啦觉得还不错的话留个赞赞在走吧
LINKS: ?

标签：int,1005,元素,XX,序列,INF,最长
From： https://www.cnblogs.com/TimelessWelkinBlog/p/17601333.html

相关文章

  • PHP反序列化例题以及Bypass总结
    unseping题目源码<?phphighlight_file(__FILE__);classease{private$method;private$args;function__construct($method,$args){$this->method=$method;$this->args=$args;}function__destruct(){......
  • [算法题python]14. 最长公共前缀
    编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 示例1：输入：strs=["flower","flow","flight"]输出："fl"示例2：输入：strs=["dog","racecar","car"]输出：""解释：输入不存在公共前缀。 提示：......
  • C# 反序列化乱码
    从文件反序列化到对象时，发生乱码，基本就是文件中的编码与流转到对象时的编码不一致，如以下情况： xml文件为日文编码反序列化函数Deserialize的参数为StreamReader，而StreamReader的编码与文件编码不一致，这样就会出现乱码   解决方案：1.构造StreamReader对象的时候与文件编......
  • 序列化-Serializable
    Serializable是Java中的一个接口，用于标识类的实例可以被序列化。序列化是将对象的状态转换为字节流的过程，可以将对象写入文件、传输到网络或存储在内存中。被序列化的对象可以在不同的Java虚拟机之间进行传输或保存，也可以在同一个虚拟机的不同时间点进行持久化存储和恢复。......
  • 让nlohmann json支持std::wstring和嵌套结构的序列化与反序列化
    nlohmannjson是一个star很高的C++json解析库。要让nlohmannjson支持某个类型T，只要给这个类型T实现一个偏特化的structadl_serializer<T>即可。adl_serializer是这个库里面针对泛型T预定义的适配器。而嵌套结构，本身就支持的。使用预定义的宏NLOHMANN_DEFINE_TYPE_NON_INTRUSI......
  • [转载] 解决Pycharm中右键运行python程序时出现Run ‘pytest‘ in XXX.py
    1、在Pycharm中右键运行python程序时出现Run'pytest'inXXX.py，这是进入了Pytest模式。2、解决办法进入到File-Seetings-Tools-PythonintegratedTools页面，找到Testing下的Defaulttestrunner，把Pytest设置为Unittests就可以了————————————————原文链接：ht......
  • PHP反序列化
    PHP反序列化序列化序列化的作用将对象或者数组转化为可存储/传输的字符串对象序列化O:4:"info":3:{s:4:"name";s:7:"iami233";s:6:"\x00*\x00age";s:2:"18";s:8:"\x00ctf\x00sex";s:7:"unknown";}//O:对象名的长度:"对象名"......
  • 代码随想录算法训练营第四十一天| 1143.最长公共子序列 1035.不相交的线 53. 最大
    1143.最长公共子序列  要求：可以跳过，找出来最长符合的节点难点：如何跳过了之后仍然保留之前的值思路:如果不符，并不是dp[i-1][j-2]等于之前的值，而是dp[i][j]等于它的相关节点以上很重要代码：1//要求：两个子数组，可以删减跳过，找出最长的长度2//思路：dp[n][m]代表第......
  • 2781.最长合法子字符串的长度-354
    最长合法子字符串的长度给你一个字符串word和一个字符串数组forbidden。如果一个字符串不包含forbidden中的任何字符串，我们称这个字符串是合法的。请你返回字符串word的一个最长合法子字符串的长度。子字符串指的是一个字符串中一段连续的字符，它可以为空。示例......
  • WEB漏洞—XXE&XML之利用检测绕过全解
    一.基础概念1.XMLXML被设计为传输和存储数据，XML文档结构包括XML声明、DTD文档类型定义(可选)、文档元素，其焦点是数据的内容，其把数据从HTML分离，是独立于软件和硬件的信息传输工具。XXE漏洞全称XMLExternalEntityInjection，即xml外部实体注入漏洞，XXE漏洞发生在应用程序解析XML......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99