P1020 [NOIP1999 提高组] 导弹拦截

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N], dp[N], ms[N];

int main() {
	int n = 1;
	while (cin >> a[n]) {
		n++;
	}
	n--;
	// 第一问
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[j] >= a[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ret = max(ret, dp[i]);
	}
	printf("%d\n", ret);
	// 第二问
	int idx = 0;
	ms[0] = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++) {
		int mn = 0;
		for (int j = 1; j <= idx; j++) {
			if (ms[j] >= a[i]) {
				if (ms[mn] > ms[j]) {
					mn = j;
				}
			}
		}
		if (mn == 0) {
			idx++;
			ms[idx] = a[i];
		} else {
			ms[mn] = a[i];
		}
	}
	printf("%d", idx);
	return 0;
}

先看了一眼题解后写的，不会优化了（虽然100分了XD