导弹拦截( 二分+dilworth定理）

https://www.luogu.org/problemnew/show/P1020 原题

接下来是dilworth定理

https://blog.csdn.net/u011676717/article/details/11842809

关键就是：  如果是求下降子序列的最小划分，相当于是求最小反链划分，等于最长不下降子序列的长度。

。。求 下降子序列的最小划分  等于最长非下降子序列长度（确定

　　求非上升子序列的最小划分  等于最长非下降子序列长度还是等于最长上升子序列长度？ 。。。

 const int INF= 0x3f3f3f3f;

 int a[N];

 int q[N],book[N]={};

 int main()

 {

     memset(q,INF,sizeof(q));

     int cnt=;

     while(cin>>a[cnt]) cnt++;

     for(int i=cnt-;i>=;i--)

         *upper_bound(q,q+cnt,a[i])=a[i];

     /* lower和upper的这两个函数原来要求是升序，题目要求降序， 于是就从i=cnt-1

        开始，从后往前升序，upper是找到大于a[i]的第一个 ，因为题目的要求是非升序，存在等于的情况

     */

     cout<<lower_bound(q,q+cnt,INF)-q<<endl;//这里还是lower

     memset(q,INF,sizeof(q));

     for(int i=;i<cnt;i++)

         *lower_bound(q,q+cnt,a[i])=a[i];  //这里用>=没毛病

     cout<<lower_bound(q,q+cnt,INF)-q<<endl;

 }