动态规划DP 最长上升子序列模型 拦截导弹（题目分析+C++完整代码）

概览检索
动态规划DP 最长上升子序列模型

拦截导弹

原题链接

AcWiing 1010. 拦截导弹

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式
共一行，输入导弹依次飞来的高度。

输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围
雷达给出的高度数据是不大于 30000
的正整数，导弹数不超过 1000。

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

题目分析

问题1

一套系统最多能拦截的导弹数？
每一发炮弹的高度不能高于前一发炮弹的高度则要求炮弹的高度单调递减，即为最长下降子序列的长度，由此转化为最长上升子序列模型LIS（点击链接跳转）。

最长上升子序列算法模板示例如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];  //a存储原始数据，f存储状态
/*要求：给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少*/
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    //遍历以a[i]结尾的序列
    for(int i=1;i<=n;i++){
        f[i]=1;  //该序列中只有a[i]，以a[i]结尾,长度为1
        //遍历在以a[i]结尾的序列下，倒数第二个数（即前一个数）为a[j]的序列
        for(int j=1;j<i;j++)
            if(a[j]<a[i])  //如果满足递增（前一个个数a[j]大于当前数a[i]）
                f[i]=max(f[i],f[j]+1);  //则进行更新，取最大值
    }
    int res=0;
    //遍历以a[0]~a[n]结尾的最大上升子序列，其中的最大值即为所求值
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    printf("%d",res);
    return 0;
}

问题2

拦截所有导弹最少要配备的系统数？
解决办法：贪心

思考过程：
第一个导弹：需要一个新系统拦截
第二个导弹：
两种选择：
1.可以用已有的系统拦截，接在现有的子序列之后；
2.建造一个新系统来拦截；
无论哪种选择，这个导弹就会成为某个现有子序列的结尾。

当我们选择到第k个导弹时，前面已经建造了m个系统，即有m个下降序列，此时，我们面临着选择哪个系统（即接在哪个序列的后面）。
易知，序列结尾的数越大，在他后面能接上的数肯定就越多。因此，我们选择标准就是选择序列后，使剩余序列结尾的数尽可能的大。
因此，我们就要选择当前m个序列中，满足序列结尾数大于等于当前第k个导弹高度的所有序列中，序列结尾数最小的那个序列（这样，选择较小的，剩下的序列结尾数就相对较大）。
如果当前不存在大于等于当前数的序列结尾数（即当前数不能放在任何序列的后面），则新建造一个新系统。

总结：
从前往后扫描每一个数，对于每个数：
情况1：如果当前所有子序列的结尾都小于当前数，则创建新的子序列；
情况2：否则，将当前数放到结尾大于等于它且最小子序列后面；

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n;
int a[N];
int f[N],g[N];
int main(){
    while(cin>>a[n]) n++;
    //问题1：最长下降子序列
    //f存储最长子序列的长度
    int res=0;
    for(int i=0;i<n;i++){
        f[i]=1;
        for(int j=0;j<i;j++){
            if(a[j]>=a[i])  //与上升"<="的区别
                f[i]=max(f[i],f[j]+1);
        }
        res=max(res,f[i]);
    }
    cout<<res<<endl;
    
    //问题2：最少系统数 贪心
    //g存储序列的结尾数
    int cnt=0;  //cnt存储总系统数
    //依次遍历每一个数
    for(int i=0;i<n;i++){
        int k=0;
        //遍历当前所有的子序列，找到满足序列结尾g[i]大于等于当前数a[i]的序列
        while(k<cnt&&g[k]<a[i]) k++;
        //情况1：找到满足要求的序列，放到序列结尾，更新当前序列结尾数
        //情况2：未找到满足要求的序列，此时k>=cnt，新建拦截系统，更新序列结尾数，更新总系统数cnt
        g[k]=a[i];  //更新序列结尾数  
        if(k>=cnt) cnt++;  //若为情况2，系统总数+1
    }
    cout<<cnt<<endl;
    return 0;
}