[NOIP 1999 提高组] 导弹拦截

知识点

最长不升子序列、最长上升子序列、二分查找

解题思路

第一问求最长不升子序列，将高度取负后用upper_bound维护最长不降子序列。第二问由序列链覆盖定理等于最长严格上升子序列，用lower_bound维护。

正确性说明

一套系统可选的高度序列恰为不升子序列，取负后转为不降。严格上升子序列中的每对先后导弹都不能分到同一系统，故其长度是下界；每次把高度放入末尾高度不小于它且最小的一组，可以达到该下界，这是链覆盖与反链的等价关系。因此两项长度分别是答案。

易错点

第一问允许相等，用upper_bound；第二问严格上升，用lower_bound；读到文件结束，不存在首行数量。

复杂度

时间O(n log n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);vector<int>down,up;int x;while(cin>>x){auto i=upper_bound(down.begin(),down.end(),-x);if(i==down.end())down.push_back(-x);else *i=-x;auto j=lower_bound(up.begin(),up.end(),x);if(j==up.end())up.push_back(x);else *j=x;}cout<<down.size()<<'\n'<<up.size()<<'\n';}