题解 | #拦截导弹#

#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
int dp[1024];
//第一次拦截的是i号导弹,最多能拦截的导弹数
int f(int i, int n) {
	if (i == n - 1) {
		dp[i] = 1;
		return 1;
	}
	if (dp[i] != 0)return dp[i];
	//核心递推
	int _max = 0;
	int max_pos = i;
	for (int pos = i + 1; pos < n; pos++) {//找到右侧可拦截的，且起始拦截数最多（）的导弹
		//cout << dp[pos] << "," << _max << "," << a[pos] << endl;
		if ( f(pos,n) > _max  &&(a[i] >= a[pos])) {
			//cout << "窗口1" << endl;
			_max = f(pos,n);
			max_pos = pos;
		}
	}
	if (_max == 0) {
		dp[i] = 1;
		return 1;//右侧没有可拦截导弹
	}
	dp[i] = f(max_pos,n) +1;
	return dp[i];

	
}
int main() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int max = f(0,n);
		for (int i = 0; i < n; i++) {
			int temp = f(i,n);
			if (max < temp)max = temp;
			//cout << f(i, n) << ",";
		}
		//cout << endl;
		cout << max << endl;
	}
	return 0;
}