主要内容 #

• 拦截导弹
• 求解思路
• 参考代码

1. 拦截导弹问题描述 #

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于1000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
数据范围：导弹个数 n 满足 1<=n<=1000;，导弹的高度 m 满足 1<=m<=1000;
输入描述
第一行输入一个正整数 n ，表示导弹的个数
第二行输入 n 个正整数，表示导弹的高度
输出描述
输出一套拦截系统最多拦截多少导弹和最少要配备多少套导弹拦截系统两个正整数
输入样例
8
389 207 155 300 299 170 158 65
样例输出
6
2

2. 求解思路 #

将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。这一部分内容上节课已经讲过了。
参考代码如下：

for(int i=t-1;i>=1;i--){//最长下降子序列
      dp[i]=1;//初始化为1
      for(int j=i+1;j<t;j++){//要反着来
          if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);//dp
      }
      maxn=max(maxn,dp[i]);//取最大
  }
  cout<<maxn<<endl;

对于第二问最直观的方法就是求完一次dp[i]后把刚才要打的导弹去掉，在求一次dp[i]直到打完所有的导弹，但这样做就错了。
不难举出反例： 6 1 7 3 2
错解： 6 3 2/1/7 正解：6 1/7 3 2
其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题，那么最长上升子序列的长度就是至少需要的导弹个数。
求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。

for(int i=1;i<t;i++){//最长上升子序列
      dp[i]=1;//初始化为1
      for(int j=1;j<i;j++){
          if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);//dp
      }
      maxn=max(maxn,dp[i]);//取最大
  }

3. 参考代码 #

#include<iostream>
using namespace std;

int dp[1000005],a[100005],maxn,t=1;
int main(){
    int n;
    cin >> n;
    for(; t <= n; ++t){
        cin >> a[t];
    }
        
    for(int i=t-1;i>=1;i--){//最长下降子序列
        dp[i]=1;//初始化为1
        for(int j=i+1;j<t;j++){//要反着来
            if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);//dp
        }
        maxn=max(maxn,dp[i]);//取最大
    }
    cout<<maxn<<endl;
    maxn=0;//记得要弄成0!
    for(int i=1;i<t;i++){//最长上升子序列
        dp[i]=1;//初始化为1
        for(int j=1;j<i;j++){
            if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);//dp
        }
        maxn=max(maxn,dp[i]);//取最大
    }
    cout<<maxn;
}