2056.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2056 on 2005-12-21 at 13:02:00 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 128;

int main()
{
	int n, h[MAX];
	int put[MAX][MAX], next[MAX][MAX];
	int i, j, k, stack[2*MAX];
	
	h[0] = 0, h[1] = MAX-1;
	while(scanf("%d", &n) != EOF && n > 0) {
		memset(put, 0, sizeof(put));
		int most = 0;
		for(i = 2; i < n+2; i++) {
			scanf("%d", &h[i]);
			int top = 0;
			for(j = 0; j < i; j++) {
				int p = 0;
				if(h[j] <= h[i]) {
					for(k = 0; k < i; k++) {
						if(h[k] >= h[i]) {
							p = max(p, put[h[j]][h[k]]+1);
						}
					}
					stack[top++] = h[j] * MAX + h[i];
					next[h[j]][h[i]] = p;
				}
				if(h[j] >= h[i]) {
					for(k = 0; k < i; k++) {
						if(h[k] <= h[i]) {
							p = max(p, put[h[k]][h[j]]+1);
						}
					}
					stack[top++] = h[i] * MAX + h[j];
					next[h[i]][h[j]] = p;
				}
				most = max(most, p);
			}
			for(j = 0; j < top; j++) {
				int r = stack[j] / MAX, c = stack[j] % MAX;
				put[r][c] = next[r][c];
			}
		}
		printf("At most %d book(s) can be put onto the bookshelf.\n", most);
	}
	
	return 0;
}