信息学奥赛一本通T1322-拦截导弹问题-题解（C/C++语言代码）

1. 直接说了，最多能拦截的导弹的高度是不能超过上一次的高度，所以容易能想到最多能拦截的导弹数量就是所给序列的最长不上升子序列长度（并不是最长下降子序列）。而要拦截所有导弹需要的系统数目就是所给序列的最长上升子序列的长度（也就是把最长上升子序列中每一个数字分到不同的组里面即可），另外需要注意这个必须是最长上升子序列哈~。

例如样例：389  207  155  300  299  170  158  65  111

能拦截最多的导弹是6颗：389  300  299  170  158  65

需要2台机器才能够拦截所有导弹：

第一台：389 300 299 170 258 65

第二台：207 155 111

2. 综上自己可以具体的画一画理解一下，下面具体说一下动态规划求最长上升子序列的求法：

已知序列f[N];

设dp[i]表示以f[i]结尾的最上上升子序列的长度，那么有如下状态转移方程：

dp[i] = max{dp[i], dp[j] + 1}, 0 <= j < i且f[j] < f[i];

根据上述推理过程两层for循环就可以求出最终结果。

最长不上生子序列的求解方法和最长上升子序列的方法是相同的只需将条件中的 < 

改为 >= 即可；状态转移方程如下：

dp[i] = max{dp[i], dp[j] + 1}, 0 <= j < i且f[j] >= f[i];

3. 注意：dp过程中并不是最终结果就是最优值，需要再dp过程中记录最优值。

4. 代码如下：

#include <iostream>
using namespace std;

int a[1005], n = 1, ans;
int dp[1005];

int main() {
	while (cin >> a[n]) n++;
	for (int i = 1; i < n; ++i) {
		dp[i] = 1;
		for (int j = 1; j < i; ++j) 
			if (a[i] > a[j])
				dp[i] = max(dp[i], dp[j] + 1);
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}