uva 12002 - Happy Birthday(LIS)

题目链接：uva 12002 - Happy Birthday

题目大意：给出一个序列，表示说有n个碟子，每个数字代表碟子的大小，现在开始堆碟子，可以选择在上面和下面放，不过放上面的碟子必须小于等于最上面的碟子，放在下面的碟子必须大于等于最下面的碟子。问说最多能放多少碟子。

解题思路：和uva 11456做法相似，只不过说这题可以取相同的大小，那么只需要分成两种情况考虑即可，一种是将当前起始的值归入升序中，一种是归进降序中。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 505;

int n, s[N], up[N], down[N];

void init () {

	for (int i = 1; i <= n; i++)
		scanf("%d", &s[i]);

	for (int i = n; i; i--) {
		up[i] = down[i] = 1;
		for (int j = n; j > i; j--) {
			if (s[j] <= s[i])
				down[i] = max(down[i], down[j] + 1);
			if (s[j] >= s[i])
				up[i] = max(up[i], up[j] + 1);
		}	
	}
}

int cat (int k, int p, int a) {
	int ans = 0;
	for (int i = p; i <= n; i++) {
		if (a == 1 && s[i] >= k)
			ans = max(ans, up[i]);
		if (a == -1 && s[i] <= k)
			ans = max(ans, down[i]);
	}
	return ans;
}

int solve () {
	int ans = 0;

	for (int i = 1; i <= n; i++) {
		int u = up[i] + cat(s[i]-1, i, -1);
		int v = down[i] + cat(s[i]+1, i, 1);
		ans = max(ans, max(u, v));
	}
	return ans;
}

int main () {
	while (scanf("%d", &n) == 1 && n) {
		init ();
		printf("%d\n", solve());
	}
	return 0;
}