LIS 问题
LIS,即最长上升子序列。
1. 朴素的求法
使用动态规划,\(dp_i\) 代表以第 \(i\) 位结尾的最长上升子序列长度。得动态转移方程:
\[dp_i = \max_{j < i \text{ 且 } a_i > a_j} dp_j + 1 \]Code1
#include <iostream>
using namespace std;
#define MAXN 100005
int a[MAXN],f[MAXN];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int ans=-1;
for(int i=0;i<n;i++)
{
f[i]=1;
for(int j=0;j<i;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
ans=max(f[i],ans);
}
cout<<ans<<endl;
return 0;
}
时间复杂度:\(O(n^2)\)。
2. 优化处理
维护一个数组 \(vec\),\(vec_i\) 表示长度为 \(i+1\) 的 LIS 的最小的终点。
长度相同的 LIS 只存终点的最小值。
随着 LIS 长度的增加,其结尾的值(最小的那个)一定是单调递增的。比如:长度为 \(4\) 的 LIS 的终点值 \(<\) 长度为 \(5\) 的 LIS 的终点值。
该策略是让小元素尽可能更新在前面,替换掉前面的大元素,这是因为前面的数越小,LIS 的长度才可能越长。
举例 \(a = [1,5,2,3,4,6]\)。
更新 \(vec\) 过程如下:
- 第一个 \(1\) 来,\(vec_0 = 1\) 此时 \(vec=[1]\)。
- 第二个 \(5\) 来,因为 \(5 > 1\),\(vec\) 拓展,\(vec_1 = 5\),此时 \(vec = [1,5]\)。
- 第三个 \(2\) 来,而 \(2 < 5\),替换之,\(vec_1 = 2\),此时 \(vec = [1,2]\)。
- 第四个 \(3\) 来,因为 \(3 > 2\),\(vec\) 拓展,\(vec_2 = 3\),此时 \(vec = [1,2,3]\)。
- 第五个 \(4\) 来,因为 \(4 > 3\),\(vec\) 拓展,\(vec_3 = 4\),此时 \(vec = [1,2,3,4]\)。
- 第六个 \(6\) 来,因为 \(6 > 4\),\(vec\) 拓展,\(vec_4 = 6\),此时 \(vec = [1,2,3,4,6]\)。
最后返回 \(vec\) 数组的长度 \(LIS = 5\)
Code2
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100005
#define inf 2147483647
int n,a[MAXN],tot;
vector<int> vec;
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
int tem=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();
if(tem==vec.size())
vec.push_back(a[i]);
else vec[tem]=a[i];
}
cout<<vec.size();
return 0;
}
类似的,其他几种 LIS 求法如下:
- 最长下降子序列:进行
reverse
操作。 - 最长不增子序列:
lower_bound
变为upper_bound
。 - 最长不降子序列:进行
reverse
操作并将lower_bound
变为upper_bound
。
练习
原文链接:
https://blog.csdn.net/shizheng_Li/article/details/105572886
标签:int,问题,MAXN,vec,LIS,长度,include From: https://www.cnblogs.com/zhangyuyi1218/p/-/LIS_problem