UVA - 12002 Happy Birthday

Description

Happy Birthday

Today it's February 13th. It's a very special day: Miguel's birthday! Like every year, he's organised a big celebration for all his friends. He prepared a succulent dinner at his house. Everyone had a lot of fun and the celebration was a complete success.

Now it's time for the not-so-funny cleaning up. He wants to start with moving all the dishes from the table to the kitchen. Since he's been going to the gym lately, he feels strong enough to pile and carry at once as many dishes as he wants. Time doesn't go unnoticed though: he's not as agile as he used to be, so he can only carry the stack of dishes if it's completely stable. A stack of dishes is stable if each dish on the stack is bigger or equal in size than all the dishes above it. If the stack wasn't stable he would drop the dishes and would have even more things to clean!

At the beginning of the scene, Miguel is empty-handed in one side of the table, walks along the table finding and maybe collecting dishes of different sizes until he reaches the other side, and then brings the collected dishes to the kitchen. When he finds a dish, he can:

ignore the dish. if he has empty hands, pick up the dish. if he has a stack of dishes on his hands, pile the dish on top of the stack. if he has a stack of dishes on his hands, put the stack on top of the dish, then pick up the new stack (including the dish).

Miguel is tired, so he wants to clean up the table as soon as possible. He'd like to take as many dishes as he can in each run, but he's exhausted from the party and can't think clearly. He's asked you for help to find out what the maximum number of dishes he can collect in a single run is.

Input

Input contains several datasets. Each dataset consists on two lines. The first line of each dataset contains an integer N ( 1N500), the number of dishes on the table. The second line of each dataset contains N integers, k₁...k_N ( 1k_i1000), specifying the size of each dish he finds, in the same order he finds them. Input ends with a dataset with N = 0. This case shouldn't be processed.

Output

For each dataset, print the maximum number of dishes Miguel can collect in a single run.

Sample Input

6
3 1 5 6 2 4
6
3 4 2 5 2 6
0

Sample Output

4
6
題意： 有n個盤子，依次選過去，你可以選或者不選，也可以放在堆的上面或者下面，但是必須滿足上面的盤子是小於等於下面的盤子的，求最長是多少
思路： 首先我們從後面做LIS和LDS，然後就可以想如果我們從第i個開始拿的話，那麼我們可以在遇到它之後大於它的盤子j，那麼我們需要找的就是以較大為起點的LIS，再加上
小的LDS；遇到小的話，情況相反。簡單來說就是讓大的更大，小的更小，起初正著做會錯
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1005;

int lis[maxn], lds[maxn];
int n, num[maxn];

int main() {
	while (scanf("%d", &n) != EOF && n) {
		memset(lis, 0, sizeof(lis));
		memset(lds, 0, sizeof(lds));
		for (int i = 1; i <= n; i++) 
			scanf("%d", &num[i]);

		for (int i = n; i >= 1; i--) {
			lis[i] = lds[i] = 1;
			for (int j = n; j > i; j--) {
				if (num[i] >= num[j])
					lds[i] = max(lds[i], lds[j] + 1);
				if (num[i] <= num[j]) 
					lis[i] = max(lis[i], lis[j] + 1);
			}
		}

		int ans = -1;
		for (int i = 1; i <= n; i++) {
			ans = max(ans, max(lis[i], lds[i]));
			for (int j = i+1; j <= n; j++) {
				if (num[j] < num[i])
					ans = max(ans, lis[i] + lds[j]);
				else if (num[j] > num[i])
					ans = max(ans, lds[i] + lis[j]);
			}
		}

		printf("%d\n", ans);
	}
	return 0;
}