AcWing 1010. 拦截导弹
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2
第一问不是最难的点，最难的是怎么找能覆盖整个序列的最少的不上升子序列的个数。
然后我借鉴了这个大佬的博文。
用如下方式维护数组s，数组长度cnt，意为cnt个不下降子序列。保存的是每一个不上升子序列中的最后一个数：
遍历原序列，对于遍历到的每一个数x：
1.若x大于s中每一个数，则新建一个不上升子序列，放入x;
2.否则，找到s中大于等于x的最小的数，将其替换。
由于s每次增加长度时，增加的数必然大于其前面s中的任何一个数；且每次替换时，不改变x与被替换数左右相邻两数的相对大小关系，故s必然维持单调递增。则s即为原序列的最长上升子序列。
即证明了：
“能覆盖整个序列的最少的不上升子序列的个数”等价于“该序列的最长上升子序列长度”
同理即有：
“能覆盖整个序列的最少的不下降子序列的个数”等价于“该序列的最长下降子序列长度”
（欲深究可研读离散数学中的Dilworth定理）
下面证明上述贪心算法的正确性：
设A为用该贪心算法得到的方案，B为最优解方案。记A的不上升子序列个数为la，B的不上升子序列个数为lb。
显然lb<=la（否则B就不是最优解）。
故只需证明la>=lb。用调整法(微调法)。
若A=B，则la=lb，显然成立。
否则（即A!=B），必然可以找到两方案中第一个(以原序列的顺序)不同之处（某数放在了不同的位置，且原序列中该数前的所有数在两方案中放的位置皆相同），将该数在两方案中所处的位置上的数(即该数本身)以及两位置之后方案中的序列相互对调，结果所得方案仍为合法解。即我们将贪心算法所得方案调整成了最优方案，且在调整过程中，方案的序列数没有增加，故la>=lb（la -> lb，且la转变为lb的过程中la的大小没有增加）。
证毕！
作者：玖梦づ
链接：https://www.acwing.com/solution/content/6746/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
最后代码如下：
#include<iostream>using namespace std;const int N=1010;int n;int f[N],p[N],t[N];int main(void)
{
while(cin>>p[n]) n++;int res=0;for(int i=0;i<n;i++){
f[i]=1;for(int j=0;j<i;j++)if(p[j]>=p[i])f[i]=max(f[i],f[j]+1);res=max(res,f[i]);}cout<<res<<endl;int cnt=0;for(int i=0;i<n;i++){
int k=0;while(k<cnt&&t[k]<p[i]) k++;t[k]=p[i];if(k>=cnt)cnt++;}cout<<cnt<<endl;
}