先来抛个经典题目

Description

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是$\leq 50000$的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

Sample Input

389 207 155 300 299 170 158 65

Sample Output

6

2

Solution

经典的导弹拦截题目，经典的线性$DP$，设$dp[i]$表示以第$i$位置开头的最长长度，容易得出状态转移方程$dp[i]=max(dp[i],dp[j]+1)(i+1\leq j\leq n)$，需要注意的是，$i$要从$n$循环到$1$，因为状态转移时需要保证$i$后面的$dp$值已经预处理好才能进行转移，时间复杂度$O(n^2)$

先抛个第一问的代码

关于第二问，抛开问题不谈，先来介绍一下离散数学中的几个概念和定理。

①偏序关系：设$R$是集合$A$上的一个二元关系，若$R$满足自反性、反对称性和传递性，则称$R$是$A$上的偏序关系。

以样例输入为例，集合$A=\{ 389,207,155,300,299,170,158,65\}$，则二元关系$R$用关系矩阵表示如下所示。

$M _R=\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 &1\end{bmatrix}$

显然二元关系$R$满足自反性、反对称性和传递性，是偏序关系。

②可比、不可比：设$(A,\preceq )$是一个偏序集，对于任意的$x,y\in A$，若$x\preceq y$或$y\preceq x$，则称$x$和$y$可比，否则就称它们不可比。

③链、反链：设$(A,\preceq )$是一个偏序集，$B$是$A$的一个子集，如果$B$中任意两个元素可比，则$(B,\preceq )$是一条链，如果$B$中任意两个元素不可比，则$(B,\preceq )$是一条反链。

④$Dilworth$定理：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。

其对偶形式：对于任意有限偏序集，其最长链中元素的数目必等于最小反链划分中反链的数目。

由此可见，题目的第二问就是求最小链划分中链的数目，而第一问我们已经求出最大链中元素的数目，所以由$Dilworth$定理可得，我们再求出最大反链中元素的数目就是第二问的答案，只需再$DP$一次即可。

第二问代码

至于$Dilworth$定理的证明，这里便不再赘述，有时间会写一篇总结（等想起来再说吧233）

下面介绍一下$nlogn$的做法（划重点！！！）

花里胡哨的方法下面有，这里先说最浅显易懂的

维护一个单调不增的单调栈$S$，最终我们想要这个栈里存储的元素个数就是第一问的答案，那么我们每遇到一个高度时就和栈顶元素进行比较，这里我们假设该高度为$x$，栈顶元素为$S[top]$，如果$x<=S[top]$，说明现在的高度能够直接接在栈的后面，那么我们直接$S[++len]=x$，$len$为栈内元素个数，如果$x>S[top]$，发扬瞎搞精神，没有条件创造条件也要上，由于栈内元素是有序的，二分查找出栈内第一个小于等于$x$的元素，把这个元素踹掉换成$x$。

为什么这样做是正确的呢？

我们可以这样想，假设二分查找找到的第一个小于等于$x$的元素为$y$，如果$y$在栈顶，那么直接替换就好了，因为替换后的栈顶元素工作能力比之前的强，后面可能能接上更多的元素，如果$y$不在栈顶，那么我们可以直接替换掉它，因为$y$后面不可能再用到了，既然这个位置注定存在，那么我们这里放$y$还是放$x$都无所谓。

放一个第一问$nlogn$的代码，第二问的代码就不需要了，按照上面的定理再用同样方法做就OK了。

Special

多加了个$Special$模块，专门列一些大犇们的做法，真的是绝了！

法一：线段树/树状数组优化$DP$

注意到导弹的高度都是不超过$50000$的正整数，可以以导弹高度为下标建立线段树，为什么不直接以序列下标建线段树呢？我们可以看到，方程转移是有条件的，符合条件才进行转移，如果我们去判断是否能够转移，那么时间复杂度还是$O(n^2)$，并没有起到优化的效果，所以我们只能另辟蹊径，直接以导弹高度建立线段树，这样转移的时候直接查询$\leq a[i]$的最大值即可，晚上想了好久为什么这样是正确的，万一序列里有比当前高度大且比它靠前的存在呢，结果发现这种担心完全是多余的，我们是从后往前循环，每个循环的点的状态只与序列里比它靠后的有关，虽然比它靠前的比它高度高，但是还没转移到，当然不会对当前转移产生影响。后来我又想了一个问题(我为什么老是自己给自己找麻烦)，就是这个线段树到底是建立在什么基础上的，往常我们使用线段树是直接针对想要操作的序列建的，而针对这个问题，线段树很明显是想要操作$dp$值，但是下标又是导弹高度，后来想明白对于这个序列，它的高度、序列下标和$dp$值一体的，也就是说，我们想要操作一个$dp$值的时候，这个$dp$值必定对应着一个导弹高度和一个序列下标，所以我们这个线段树里面的值虽然是对应区间$dp$值的最大值，但是我们转移的时候在循环中已经利用该$dp$值所对应的导弹高度和序列下标作出了是否能够转移的判断，线段树的作用仅仅是转移。

需要注意的是，这里初始的$dp$值不是$1$而是$0$了，为什么会出现这种情况，因为之前我们状态转移的时候是以序列下标为下标进行转移的，所以并不存在重复的情况，而我们以导弹高度为下标的时候，导弹高度可能存在重复的情况，我们将初始值设为$0$，那么进行转移的时候，假如该点序列后面没有比该点高度小的话，那么在方程$dp[i]=max(dp[i],dp[j]+1)$中，$dp[i]$的值应该是不变的，然而$dp[i]$的值本身就应该是$1$，所以这里我们直接查询出$\leq a[i]$再加$1$就能满足转移方程的所有情况。

第二问就不说了，还是上面那个定理。

法二：最小路径覆盖

此法针对第二问，我们把每个导弹拦截系统能够拦截的导弹按照顺序排在一起，这些导弹构成了一条链，那么我们可以把这条链抽象到图论上，我们假设这些导弹构成了一张图，也就是说每个$x\preceq y$我们都连一条$x$->$y$的边，那么我们就能得到一张$DAG$(有向无环图)，那么第二问所求的就是求$DAG$中的最小不相交路径覆盖。

首先我们需要拆点，将每个点$x$拆成出点$x1$和入点$x2$，分别对应着出边和入边，然后根据导弹之间的高度关系进行连边，对于每一条边都是$x1$向$y2$连一条边，这样连边和原先的$DAG$是等价的，因为点与点之间的连接关系没有改变，只是把一个点拆成了入点和出点，为什么要这样连边呢？因为我们要将有向图变成二分图。

因为我们要求$DAG$的最小不相交路径覆盖，而最小路径覆盖=点数-最大匹配数，为什么呢？假设我们一开始没有任何连边，那么我们要实现最小覆盖的路径数是点数$n$，每当我们在二分图中获得一个匹配，相当于在两个点连了一条边，那么路径数就要减$1$，而我们前面的拆点操作正好能够保证该点作为中介点的可能性，假设该点是中介点，正因为入点和出点正好在图的两边，它们有可能成为最大匹配方案中的两条边，那么正好能够形成一个以该点为中介点的通路，这就是把有向图变成二分图的必要性。

用网络流匈牙利算法均可，匈牙利算法的时间复杂度为$O(VE)$，其中$V$是二分图中左边点的个数，$E$是二分图中边的个数。