P1020 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

解答

第一问：求数列的最长不上升子序列长度

第二问：求最少的不上升子序列覆盖数

根据 Dilworth 定理，最少的不上升子序列覆盖数等于 最长上升子序列 (Longest Increasing Subsequence, LIS) 的长度，因此两个问题可以相互转化。

先说算法：

1. 第一问（最长不上升子序列）：
   • 维护一个非递增的辅助数组 dp1。
   • 如果当前元素 M[i] 小于等于 dp1 的最后一个元素，直接追加。
   • 否则，用 upper_bound 在 dp1 中找到第一个小于 M[i] 的数并替换它。这样可以让子序列更有潜力接纳更多元素。
   • 最终 dp1.size() 就是答案。
2. 第二问（最少系统数 = 最长上升子序列）：
   • 维护一个递增的辅助数组 dp2。
   • 如果当前元素 M[i] 大于 dp2 的最后一个元素，直接追加。
   • 否则，用 lower_bound 在 dp2 中找到第一个大于等于 M[i] 的数并替换它。
   • 最终 dp2.size() 就是答案。

第二问比较容易用贪心的思路来理解：

将dp数组的值看成目前用过的所有导弹高度的上限，按顺序遍历所有目标，

• 每次选取满足要求且上一发打得最低的导弹来打新的目标，这样减少浪费，保证这一发打完以后各个导弹的上限最高。
• 如果下一个目标比之前所有导弹上一发都高，只能新开一个导弹。

打完以后将导弹的高度上限改为这个目标的高度。正好，无论对已有的导弹还是新增的导弹，更新为新的目标的高度后均能保持数组仍然单调递增，为运用二分查找提供了条件。

Dilworth 定理暗示着第一问也能使用类似的方法，但不如第二问直观。读者可尝试自行解释。我的一种解释是：将此时的 dp 数组看作所求的最长单调子序列的变体，

• 当下一个元素比最后一个元素小时，自然可以直接加入子序列，使长度 +1 。
• 否则，找到该元素可以出现的最晚的位置，把它放在这里，使该处的值变大，使得以后更多元素（大于原来值但不大于新的值的元素）可以接在它后面。

这样，dp 第 i 位表示长度为 i 时，最后一个元素的上限。

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mm = 100100;
vector<int> v1,v2;
int n, h[mm];

bool rev(const int &a, const int &b){
  return a>b;
}

int main(){
  int tmp;
  while (cin>>tmp) {
    h[n++]=tmp;
  }
  
  v1.push_back(h[0]);
  for (int i=1; i<n; i++) {
    if(h[i]<=v1.back()) {
      v1.push_back(h[i]);
      continue;
    }
    auto p=upper_bound(v1.begin(), v1.end(), h[i], rev);
    *p=h[i];
  }
  cout<<v1.size()<<endl;

  v2.push_back(h[1]);
  for (int i=0; i<n; i++) {
    if(h[i]>v2.back()) {
      v2.push_back(h[i]);
      continue;
    }
    auto p=lower_bound(v2.begin(), v2.end(), h[i]);
    *p=h[i];
  }
  cout<<v2.size();

  return 0;
}

相关题