P1020 导弹拦截

第一问：以后每一发炮弹都不能高于前一发的高度

  • 求最长不上升子序列长度，不再概述

第二问：拦截所有导弹最少要配备多少套这种导弹拦截系统(最少需要几个最长不上升子序列)

法一：贪心

  • 从前往后遍历，取该值x,cnt表示子序列个数
  • 遍历所有（0~cnt-1）子序列，如果x大于当前子序列的最小值，就取找下一个子序列
  • 把该值放到当前位置k
  • 当前位置为cnt，那就需要新开一个序列 
int cnt = 0;
    for(int i = 0; i < n; i ++ ){
        int k = 0;
        while(k < cnt && g[k] < a[i]) k ++;
        g[k] = a[i];
        if(k == cnt) cnt ++;
    }
    cout<<cnt<<endl;

法二：Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度。

  • Dilworth定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度。
  • 把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。
    res = 0;
  for(int i = 1; i <= n; i ++ ){
      f[i] = 1;
      for(int j = 1; j < i; j ++ ){
          if(a[i] > a[j]){
              f[i] = max(f[i],f[j] + 1);
          }
      }
      res = max(res,f[i]);
  }
  cout<<res<<endl;