【例6.4】拦截导弹问题(Noip1999)

这个问题可以使用动态规划来解决。我们需要找到最小的系统数量，以拦截所有导弹。每一套系统都需要满足条件：第一发炮弹能够到达任意的高度，但之后每一发炮弹的高度都不能超过前一发。

我们可以使用两个数组：dp1 和 dp2。dp1[i] 表示拦截前 i 个导弹所需的最少系统数，并且考虑第 i 个导弹作为新的一套系统的最高点。dp2[i] 则表示拦截前 i 个导弹时，最后一个系统的最高点所能达到的最大高度。

算法步骤：

初始化 dp1 和 dp2 为无穷大，除了dp1[0]=0 （没有导弹时不需要系统）。
遍历每一个导弹的高度h[i] 。
对于每个 i，再次遍历之前的导弹高度 h[j]（j 从 0 到 i-1）。
如果 h[j] >= h[i]，则考虑将第 i 个导弹放入以第 j 个导弹为最高点的系统中。此时，dp1[i] 的值更新为 min(dp1[i], dp1[j] + 1)，同时更新 dp2[i] 为 h[i]。
如果 h[j] < h[i]，则第 i 个导弹必须作为新的一套系统的最高点，此时 dp1[i] 的值更新为 min(dp1[i], dp1[j])，并且 dp2[i] 保持不变（因为 h[i] 是新系统的最高点）。
最终答案即为 dp1[n]，其中 n 是导弹的数量。

以下是 C++ 代码实现：

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <climits>  
  
using namespace std;  
  
int main() {  
    int n;  
    cin >> n;  
    vector<int> h(n);  
    for (int i = 0; i < n; ++i) {  
        cin >> h[i];  
    }  
  
    vector<int> dp1(n, INT_MAX), dp2(n, 0);  
    dp1[0] = 1; // 初始状态，一个导弹需要一套系统  
  
    for (int i = 1; i < n; ++i) {  
        dp1[i] = dp1[i - 1] + 1; // 初始化，假设每个导弹都需要新的系统  
        for (int j = 0; j < i; ++j) {  
            if (h[j] >= h[i]) {  
                if (dp1[j] + 1 < dp1[i]) { // 发现更优解  
                    dp1[i] = dp1[j] + 1;  
                    dp2[i] = h[i]; // 更新最高点  
                }  
            } else {  
                // h[j] < h[i]，考虑将h[i]作为新系统的最高点  
                if (dp1[j] < dp1[i]) { // 发现更优解  
                    dp1[i] = dp1[j];  
                }  
            }  
        }  
    }  
  
    cout << dp1[n - 1] << endl; // 输出最小系统数  
    return 0;  
}