求最长不升/不降/上升/下降子序列
滑_稽
·
·
个人记录
0 前置知识
什么是子序列？
对于一个原始序列，从它里面任意取若干个元素，把它们按照在原始序列里的顺序排列好，得到的新序列就是原始序列的子序列。
下面是一个栗子：
现有一个长度为 n 的序列 A=\{A_1,A_2,\dots,A_n\}。A 的任意子序列 B 可表示为
B=\{A_{k_1},A_{k_2},\dots,A_{k_p}\}(1\le k_1<k_2<\dots<k_p\le n,1\le p\le n)
什么是最长不升/不降/上升/下降子序列？
对于一个原始序列，它的一个子序列 S 是最长不升/不降/上升/下降子序列当且仅当：
-
-
其他有性质1的子序列要么没有 S 长，要么与 S 的长度相同。
由定义可看出，一个序列的最长不升/不降/上升/下降子序列可能有多个。
这四种序列的英文表示如下（个人理解）：
-
最长不升子序列：LNIS(Longest Non-Increasing Subsequence)；
-
最长不降子序列：LNDS(Longest Non-Decreasing Subsequence)；
-
最长上升子序列：LIS(Longest Increasing Subsequence)；
-
最长下降子序列：LDS(Longest Decreasing Subsequence)。
下面是一个栗子：
原始序列
A=\{10,4,9,1,7,2,7,5,7,3,5,0,3,15,1\}\quad(1)
$A$ 的 LNDS 长度为 $5$，一个 LNDS 为 $\{4,7,7,7,15\}$。
$A$ 的 LIS 长度为 $5$，一个 LIS 为 $\{1,2,5,7,15\}$。
$A$ 的 LDS 长度为 $6$，一个 LDS 为 $\{10,9,7,5,3,0\}$。
以下将求最长不升/不降/上升/下降子序列的问题统称为最长子序列问题。
# 1 求解算法1：DP
下面以 LNIS 为例，讲解如何用动态规划的方式求解最长子序列问题。
设给定序列 $A$ 长度为 $n$，有一种 $O(n^2)$ 的dp做法。
记 $A_i$ 为给定序列的第 $i$ 个数，$dp_i$ 为**所有以 $A_i$ 结尾的单调不升子序列中最长序列的长度**，初始均为 $1$。不难得出，$dp_i$ 的转移方程为 $dp_i=\max\limits_{1\le j<i,A_j\ge A_i}\left\{dp_j+1\right\}$，LNIS 的长度即为 $\max\limits_{1\le i\le n}\{dp_i\}$。
但这还只是求 LNIS 的长度，如果要将 LNIS 的所有元素都挨个输出该怎么办呢？
首先，记 $last_i$ 为**以 $A_i$ 结尾的所有单调不升子序列中最长序列的倒数第二个元素在 $A$ 里的编号**。
其次，上代码（这部分用语言文字不太好描述）：
```cpp
int n,m=0,pos,a[maxN],dp[maxN],last[maxN],LNIS[maxN];
//省略了头文件和常数定义这类无关紧要的代码
int main(){
for(n=1;cin>>a[n];n++) dp[n]=1;n--;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]>=a[i] && dp[j]+1>dp[i])
dp[i]=dp[j]+1,last[i]=j;
for(int i=1;i<=n;i++)
if(dp[i]>m)
m=dp[i],pos=i;
for(int i=m;i>=1;i--){
LNIS[i]=a[pos];
pos=last[pos];
}
cout<<m<<endl;
for(int i=1;i<=m;i++) cout<<LNIS[i]<<" ";
return 0;
}
```
请结合注释理解一下代码，如果弄懂了如何求最长不升子序列，求其他类型的最长子序列就是手到擒来。
该算法正确性证明略。~~（其实是我不会~~
# 2 求解算法2：贪心+二分
【未完待修】
# 3 例题
# 4 参考文章
李煜东《算法竞赛进阶指南》0x51节
[求最长不下降/上升/下降/不上升子序列](https://www.cnblogs.com/acioi/p/11837911.html)
[题解 P1020 【导弹拦截】](/blog/w1049/solution-p1020)