P1020 [NOIP1999 普及组] 导弹拦截
思考
这题很显然是一道DP题，第一问就是求该序列的最长不下降子序列.
先说最长不下降子序列的\(O(n^2)\)的做法.
用\(dp_k\)表示第\(k\)位时最大的最长不下降子序列的长度，
那么我们很容易可以得到：
当\(dp_i<dp_j\)且\(i>j\)时，\(dp_i=max(dp_i,dp_j+1)\)，
代码就是：
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,res,a[500005],dp[500005];
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (cin>>a[++n]) ; //题目的读入方式，有点恶心
for (int i=1;i<=n;i++){
for (int j=i-1;j>=1;j--){
if (a[j]>a[i]) dp[i]=max(dp[i],dp[j]+1); //状态转移方程式
}
}
for (int i=1;i<=n;i++) res=max(res,dp[i]); //查找答案
cout<<res;
return 0;
}
当然，这个代码会TLE，至于为什么自己看看数据范围和时间复杂度
这个代码就是\(1\to n\)分别向前找，然后找到之前的最大的最长不下降子序列的长度，
如果自己有能力接上去，那么就更新答案，把自己也接上去.
其实听起来像\(Win7\)自带的蜘蛛纸牌，之前机房里网关了，实在无聊死在玩
就是把自己尽可能加到最长的答案上去.
那么第二个输出的东西我实在不想证明太烦了，
要涉及到偏序集、Dilworth 定理等等，实在烦.
这是佬的证明.
总之只要知道第二个答案是该序列的最长上升序列就行了.
代码我懒得贴，反正之后还要优化的.
优化
首先，我们要确认两个问题：
-
怎么优化？
-
凭什么可以这么优化？
Q1:怎么优化？
用普通的方法显然不行，所以我们只能另辟蹊径.
而这条路的指向标就是：lower_bound与upper_bound！
首先我们需要一个数组\(a\)存储从第\(1\)个到第\(n\)个导弹的高度，
一个数组\(res\)存储最长不上升子序列（当然循环过程中绝对不会是答案咯，不然我干嘛还要写代码），
还有一个变量\(t\)代表结尾位置，
我们需要把\(a\)中的元素全都放到\(res\)中去.
** 如果\(b_i\le res_t\)，那么就将\(b_i\)放到\(res_i\)之后；**
** 否则说明\(b_i\)不能接在\(res\)之后，所以我们只能把\(b_i\)放进去.**
怎么放呢？在\(res\)数组中找到第一个小于\(b_i\)的数，然后代替它.
然而最快的找法就是用upper_bound和lower_bound，因为前面说过，res内是单调不上升的.
所以，我们可以编出程序：
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,res[500005],a[500005],t=1; //记得t=1
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (cin>>a[++n]) ; //读入
n--;res[1]=a[1]; //初始化
for (int i=2;i<=n;i++){
if (res[t]>=a[i]) res[++t]=a[i];
else res[upper_bound(res+1,res+t+1,a[i],greater<int>())-res]=a[i];
/* 如果实在强迫症可以写成这样：
else{
int p=upper_bound(res+1,res+t+1,a[i],greater<int>())-res;
res[p]=a[i];
}
对于大佬，可以写成这样：
*upper_bound(res+1,res+t+1,a[i],greater<int>())=a[i];
*/
}
cout<<t;
return 0;
}
Q2: 凭什么可以这么优化？
证明
设\(res_p\)为\(res\)数组中第一个小于\(b_i\)的元素.
若\(res_p\)不在末尾，那么res_p在之后都不会被用到，且不影响\(t\)的大小，所以可以直接替换；
若\(res_p\)是在末尾，因为\(res_p<b_i\)，所以\(res_p\)之后可以接的元素个数绝对少于\(b_i\)之后可以接的元素个数，为了让答案最大化，所以可以放入\(b_i\).
再回过头看看，发现还有一个问题要解决:
最长上升子序列！
这也很好解决，使用lower_bound就行了，而且还不用改比较器.
代码如下：
CODE
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,res[500005],a[500005],t=1,ans[500005],w=1;
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (cin>>a[++n]) ;
n--;res[1]=ans[1]=a[1];
for (int i=2;i<=n;i++){
if (res[t]>=a[i]) res[++t]=a[i];
else res[upper_bound(res+1,res+t+1,a[i],greater<int>())-res]=a[i];
if (ans[w]<a[i]) ans[++w]=a[i];
else ans[lower_bound(ans+1,ans+w+1,a[i])-ans]=a[i];
}
cout<<t<<"\n"<<w;
return 0;
}