DP-导弹拦截

题目链接：[导弹拦截](http://www.luogu.org/problemnew/show/P1020 "导弹拦截") ------------------------------------------------------- 题意总结： 给出一个长度不超过100000的数列，其中的数每个是不大于50000的正整数，求这个数列的最长不降子序列（问一）以及将这个数列划分为n个不降子序列时，n的最小值（问二）。 ------------------------------------------------------- 思路： 1、对于问一直接用O（n\*logn）的方法求最长不升子序列即可。 求不升子序列的方法： [http://https://www.luogu.org/blogAdmin/article/edit/20362](http://https://www.luogu.org/blogAdmin/article/edit/20362) 2、对于问二求整个数列的最长上升子序列即可。证明如下： （1）假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。 （2）假设我们得到了最小划分的K组导弹，从第a(1<=a<=K)组导弹中任取一个导弹，必定可以从a+1组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比a+1组中任意一个导更高，在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组），同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来，连成一条上升子序列，其长度即为K; （3）设最长上升子序列长度为P，则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升)，则有 P>=K，所以K=P。