动态规划问题05_导弹拦截

• 题目描述：
  某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
  但是这种导弹拦截系统有一个缺陷：虽然它能拦截任意高度的导弹，但是每拦截一发导弹，其拦截能力就下降到只能拦截上一次拦截的导弹高度。
  某天，雷达捕捉到敌国的导弹来袭，导弹依次飞来，该拦截系统最多能拦截多少导弹呢？
• Input:
  输入若干个数据：导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，用空格分隔）。
• Output:
  1、输出这套系统最多能拦截多少导弹。
  2、输出拦截所有导弹需要的拦截系统数目

---

案例输入输出：

• Input：
  3890 2070 1550 3000 2990 1700 1580 650
• Output：
  6
2

---

#include<iostream>
#include<cstring>
using namespace std;
const int MAX = 1025;
int a[MAX],b[MAX],c[MAX];
int i,maxTp;
int n,m,x;

int main()
{
    
    memset(a,0,sizeof(a));  // 记录导弹高度
    memset(b,0,sizeof(b));  // 记录最大不下降序列长度
    memset(c,0,sizeof(c));

    i = 1;
    m = 0;  // 最多一套系统拦截的导弹数
    n = 0;  // 需要的拦截系统数

    while(cin>>a[i]){
       // 输入数据
        maxTp = 0;

        for(int j=1; j<=i-1; j++){
      // 第i枚导弹前的导弹 与 i导弹 对比
            if((a[j] >= a[i]) && (b[j]>maxTp) )
            maxTp = b[j];
        }
        // 选择最长的序列 连接
        b[i] = maxTp + 1;   // 加上 第i枚导弹

        if(b[i]>m)
            m = b[i]; // 最大拦截数

        // 至此第一个问题完成

        x = 0;  // 在循环中，x=0，而n可能会改变
        for(int j=1; j<=n; j++){
    
            if(c[j]>=a[i])
               if(x==0)
                  x = j;
               else
                  if(c[x] > c[j])
                     x = j;
        }

        if(x==0){
      // 默认至少有一套拦截系统
            n++;
            x = n;
        }
        c[x] = a[i];

        i++;  // 准备下一枚导弹
    }

    cout<<m<<endl<<n<<endl;
   return 0;
}