原题链接：P1020 导弹拦截
本题非常经典，是LIS（最长不降子序列）问题的模板题。
这一类题目虽然理解上比较简单，但问题形式多样，审题时需认真并结合一定的数学推导。
本题有两种思路，由于思路的不同导致时间复杂度也不同。下面我们开始讨论解决LIS问题的通用套路。
如何求解LIS
求解LIS问题有两种不同的方式，第一种是时间复杂度为$O(n^{2})$的DP，而另一种是基于二分查找维护单调序列的$O(n\log n)$做法。
O(n²)做法
回顾一下LIS问题的一般形式：
给定一个序列$S$，求$S$中一个最长的子序列，使这个子序列满足（严格或不严格均可）单调。
为便于讨论，我们在这里以“最长不降子序列”为例，即子序列满足不严格单调递增。
1 1 2 3 2 2 5 5Such as 这样一个数列，应用大眼观察法易证最长不降子序列为：
1 1 2 2 2 5 5长度为7。
由于对于10w规模的数据难以使用大眼观察法，考虑DP。
设d[i]为从序列开始到第i个位置的最长不降子序列长度，显然有：
$$ d[i]={\max \limits_{j \in [0,i),a[j] \le a[i]}{\{d[j]\}}} + 1 $$
初始化d[0]=1或不初始化（但需注意细节）。
时间复杂度的证明留给读者作为练习。
O(nlogn)做法
维护一个单调序列，在我们讨论的情景下就是一个不降序列，其长度等于最长不降子序列长度。
如何转化问题？考虑贪心思想。仍然采用上面的例子：
a[0]=1，序列中没有元素，直接加入。=> {1}a[1]=1，加入后仍然单调，加入。=> {1,1}a[2]=2 => {1,1,2}a[3]=3 => {1,1,2,3}a[4]=2，注意，直接加入后序列将无法维持单调，我们知道，这时序列中所有数都在这个待加入的2之前，即其中第一个比2大（由于是求最长不降子序列，可以允许相等，即搜索严格大于2的数）的数，将其修改为2，能提供的贡献，或者说提供贡献的潜力会比之前大。
正确性证明（！重要）：
假设这个修改发生在单调序列的末尾，那么皆大欢喜，用一个较小的数替换较大的，必然能够给之后的数留下更多可安排的空间；另一种情况，这个修改发生在单调序列的中间某个位置，它不会对答案的正确性产生影响，因为我们关注的是长度，而非单调序列本身，能够直接影响单调序列长度的操作只有向末尾加入元素，此时这个修改并没有影响序列末尾数字的大小，不会对后续的判断造成影响，但它安插在单调序列中事实上代表了一种潜力，即子序列的分支，例如对于1 2 3这样的序列，我的子序列既可以先选一个1，也可以先选一个2，我们肯定并保留所有的可能性，即使它用不上。说白了，这是一步远棋，是在为未来可能加入的元素考量。如果这一分支成长到了一定程度（例如最终导致单调序列末尾元素被替换），那么它对答案的贡献才体现出来。
根据上面的分析，这个单调序列中储存的不一定是最长不降子序列（甚至不一定是正确解）。看下面这个例子：
1 2 3 1请读者自己模拟序列维护的过程。不难发现最后的序列是1 1 3，它虽然与最长不降子序列等长，但甚至不是原序列的子序列！
这样转化问题能带来什么好处呢？
不难发现我们需要在直接加入无法维持单调时进行查找，找到要被替代的数（此时不妨@哆来咪·苏伊特（取而代之的蝴蝶（很糟））（逃））。这个过程有一个我们很~熟悉的高效算法可以完成——二分查找，它是$O(\log n)$的！这样的话，总时间复杂度就优化到了$O(n\log n)$！
可我不想写二分 [heimu]说得好像你会一样（嫌弃脸）[/heimu]
没问题，此时需要介绍STL的两个二分姥爷：
lower_bound函数
至少需要传3个参数，前两个跟sort一样，第三个是要查找的元素（先设为x便于叙述），如果有第四个，那就是自定义比较器了。
这个函数比较毒瘤，首先，它默认你给它的是一个（可以不严格）单调递增的序列。降序？没问题，但我们要给它一个greater<>()比较器，否则给你搜到天涯海角去。
然后说说返回值。返回一个指针，指向序列中第一个大于等于x的位置。
其实风格跟sort是一致的（废话），拿返回值减数组首指针就是在数组中的位置。
例子：1 2 2 3查2就是1 [2] 2 3这个位置。
upper_bound函数
跟lower_bound一样，唯一的区别是返回的指针指向序列中第一个大于x的位置。
例子：1 2 2 3查2就是1 2 2 [3]这个位置。
如何解决这道题
扯了老半天，最初的目的还是没达到，你说第一问是个裸的LIS我懂，第二问咋求啊？
其实，还是个LIS。
在我找工具画图的时间里边咱们先口头分析一下为啥。
[heimu]即得易见平凡，仿照上例显然，留作习题答案略，读者自证不难[/heimu]
一堆废铁导弹，我们随便划分一下，就假设k次能全部打下来⑧。（每次要尽力啊，不能说后面有可以打的不打，否则不合题意。）
随便从第1组里边找一颗导弹，第2组里一定有比它飞得高的，否则何必让第2组的小姐姐费事，第1组顺便就给收掉了，根本没第2组事（不严格单调递减啊，能打的要尽量打，不然对不起国防投入）。这样找一个严格单增序列，长度肯定是k。
下面把最长上升子序列长度算出来记为m，由前方粗体字显然，$m \ge k$；再从这个最长上升子序列考虑，任意两个元素一定不在同一组内（想一想，为什么？），从而$m \le k$，综上，$m = k$。
于是，这道题就解决了~
$O(n^{2})$做法如下
#include<cstdio>
#include<algorithm>
const int MAXN = 100007;
int a[MAXN],d[MAXN],f[MAXN];
using std::max;
int main(){
int n=0;
int ans1=0;
int ans2=0;
while(~scanf("%d",&a[n])){
int t1=0,t2=0;
for(int i=0;i<n;i++){
if(a[i]>=a[n])t1=max(t1,d[i]);
if(a[i]<a[n])t2=max(t2,f[i]);
}
d[n]=t1+1;
f[n]=t2+1;
ans1=max(ans1,d[n]);
ans2=max(ans2,f[n]);
n++;
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}$O(n \log n)$做法如下
#include<cstdio>//IO
#include<cstring>//memset
#include<algorithm>//max和二分查找
#include<functional>//greater
const int MAXN = 100007;
int a[MAXN],d[MAXN],f[MAXN];
using std::max;
using std::lower_bound;
using std::upper_bound;
using std::greater;
int main(){
int n=0;
int ans1=0;
int ans2=0;
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
while(~scanf("%d",&a[n])){
if(ans1>0&&d[ans1-1]<a[n]){
int pos=upper_bound(d,d+ans1,a[n],greater<int>())-d;
//Note: upper_bound和lower_bound均 **只处理升序**
//e.g. 1 1 2 2 3 3 4 4 4 5 5 5
//我希望查找 4
//lower_bound返回序列中第一个 大于等于 __val 的元素指针
//这时查找的结果是 位置6 => 3 3 [4] 4 4 5 5 5
//upper_bound返回序列中第一个 大于 __val 的元素指针
//这时查找的结果是 位置9 => 3 3 4 4 4 [5] 5 5
//对降序的处理？
//自定义比较器即可，使用 std::greater 即可让这些函数认为3比5大
//此处进行二分查找替换维护序列 是为了保持单调性
//~~保持单调性的原因留给读者思考~~
//此处为什么用upper_bound？
//e.g. 5 5 4 4 3 3 2 2 1 1
//此时新加入一个 4
//很显然，应该是第一个 **大于** 4 的位置
//即 5 5 4 4 [3] 3 2 2 1 1
//修改后序列保持不严格单调
//~~下面使用lower_bound的正确性证明就留给读者作为练习~~
d[pos]=a[n];
}else d[ans1++]=a[n];
if(ans2>0&&f[ans2-1]>=a[n]){
int pos=lower_bound(f,f+ans2,a[n])-f;
f[pos]=a[n];
}else f[ans2++]=a[n];
n++;
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}什么？图？哪来的图？有向图还是无向图？（装傻qwq）
好吧其实是这张，相同颜色代表同一组。
版权声明：本文是原创文章，版权归 无限UCW 所有。
本文链接：https://ucw.moe/archives/solution-luogu-p1020.html
本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。
