C++实现用动态规划的思想解决拦截导弹问题

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

输入：
第一行输入M表示包含M组测试数据，每组第一个输入N (N<100)表示后面有N个整数，表示导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)。

输出：
对于每组输入数据，第一行输出这套系统最多能拦截多少导弹，以及输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入示例：
2
7 300 250 275 252 200 138 245
7 181 205 471 782 1033 1058 1111

输出示例：
5 2
1 7

解题思路：
我们很快就能联想到是在一个数组里面寻找最长非上升子序列和最长上升序列，可以用动态规划的方法来解决这个问题。
具体思路在注释中已经很详细了，不再赘述。

代码：

//
// main.cpp
// InterceptMissiles
//
// Created by 胡昱 on 2021/10/23.
//

#include <iostream>
using namespace std;

// 记录问题的解
struct Result {
    
    int missileNum = 0;
    int systemNum = 0;
};

// 计算最多能够拦截多少导弹以及至少需要多少套系统，即最长非上升子序列长度和最长上升子序列长度
// 此算法的时间复杂度应该为 O(n^2)
Result solve(int* a, int n) {
    
    Result result;
    
    // dp1[i]指的是从0到i的最长非下降子序列长度
    int* dp1 = new int[n];
    // dp2[i]指的是从0到i的最长上升子序列长度
    int* dp2 = new int[n];
    
    for(int i = 0; i < n; ++i) {
    
        
        // 子序列最短的长度为1
        dp1[i] = 1;
        dp2[i] = 1;
        
        // 此步骤为动态规划法的核心
        // 原理为：由反证法可以得出dp[i]可以由a[i]与a[0...i-1]的大小关系以及dp[0...i-1]推得
        for(int j = 0; j < i; ++j) {
    
            if(a[i] <= a[j]) {
    
                dp1[i] = max(dp1[i], dp1[j] + 1);
            }
            else {
    
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
        
        // 记录解。如果没有这一步则后面还需要一个循环来判断最大值，麻烦！
        result.missileNum = max(result.missileNum, dp1[i]);
        result.systemNum = max(result.systemNum, dp2[i]);
    }
    
    
    delete [] dp1;
    delete [] dp2;
    
    return result;
}

int main(int argc, const char * argv[]) {
    
    
    // 共m个问题
    int m;
    cin >> m;
    while((m--) > 0) {
    
        
        // 输入数组长度n
        int n;
        cin >> n;
        
        // 输入数组
        int* a = new int[n];
        for(int i = 0; i < n; ++i) {
    
            cin >> a[i];
        }
        
        // 输出结果
        Result result = solve(a, n);
        cout << result.missileNum << " " << result.systemNum << endl;
        
        // 释放资源
        delete [] a;
    }
}