@
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\) 无论如何变化，始终保持单调递增
这样，我们便可以得到如下操作：
初始化 \(b\) 为 INF，\(cnt\) 设为 0 （表示目前最长上升子序列的最长长度，也是 \(b\) 中最后一个不为 INF 的位置）
得到一个 \(a_i\) ，若它比 \(b_{cnt}\) 大，则把它作为新的元素，\(cnt \leftarrow cnt+1 , b_{cnt} \leftarrow a_i\) 。否则二分查找第一个大于等于该值的元素 \(b_j\) ，替换 \(b_j \leftarrow a_i\)
重复执行操作 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: