拦截导弹(Noip1999)

经典dp题目，这个做法并非最优解，详细参考洛谷导弹拦截，想想200分的做法。

#include <iostream>

#include <cstdio>

using namespace std;

//Mystery_Sky

//最长不上升序列+最长不下降序列

#define M 1010

int f_down[M], f_up[M], a[M], n;

int ans_down, ans_up;

int main() {

	while(cin >> a[++n]) f_down[n] = f_up[n] = 1;

	n--;

	for(int i = 2; i <= n; i++)

		for(int j = 1; j < i; j++) {

			if(a[i] > a[j]) f_up[i] = max(f_up[i], f_up[j]+1);

			if(a[i] <= a[j]) f_down[i] = max(f_down[i], f_down[j]+1);

		}

	for(int i = 1; i <= n; i++) {

		ans_down = max(ans_down, f_down[i]);

		ans_up = max(ans_up, f_up[i]);

	}

	printf("%d\n%d", ans_down, ans_up);

	return 0;

}

巴特西

一本通 1260：【例9.4】拦截导弹(Noip1999)

拦截导弹(Noip1999)

最新文章

热门文章