狗狗40题搞完纪念 » 1021

1021
1021.cpp


#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 256;

int main() {
	int ri = 0, n, ans, sum[MAXN];
	int dp[MAXN][MAXN];
	char buf[MAXN][MAXN];

	sum[0] = 0;
	for (int i = 1; i < MAXN; ++i) {
		sum[i] = sum[i - 1] + i + i - 1;
	}
	while (scanf("%d", &n) != EOF && n > 0) {
		for (int i = n - 1; i >= 0; --i) {
			scanf("%s", buf[i]);
		}
		ans = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 1; j < i + i + 1; j += 2) {
				if (buf[i][j] == '#') {
					dp[i][j] = 0;
				} else if (buf[i - 1][j - 1] == '-' && 0 <= j - 2 && j < i + i - 1) {
					dp[i][j] = min(dp[i - 1][j - 2], dp[i - 1][j]) + 1;
				} else {
					dp[i][j] = 1;
				}
				ans = max(ans, dp[i][j]);
			}
		}
		for (int i = n - 1; i >= 0; --i) {
			for (int j = 0; j < i + i + 1; j += 2) {
				if (buf[i][j] == '#') {
					dp[i][j] = 0;
				} else if (i + 1 < n && buf[i + 1][j + 1] == '-') {
					dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 2]) + 1;
				} else {
					dp[i][j] = 1;
				}
				ans = max(ans, dp[i][j]);
			}
		}
		printf("Triangle #%d\nThe largest triangle area is %d.\n\n", ++ri, sum[ans]);
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//296 	2010-06-27 07:12:35 	Accepted 	1021 	C++ 	0 	180 	anotherpeg 	Source
Leave a Reply