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

本文主要是介绍【例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;  
}