UVa 585 - Triangles

链接

传送门

题意

给出一个三角形,输出由“-”组成的最大的三角形的面积。

思路

区分奇偶进行记忆化搜索。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 210;
char s[maxn][maxn];
int n, t;
int d[maxn][maxn], u[maxn][maxn];
int DP(int i, int j, int x, int dp[][maxn]) {
int& k = dp[i][j];
if (k != -1) {
return k;
}
if (s[i][j] != '-') {
return k = 0;
}
i += x;
k = min(min(DP(i, j - 1, x, dp), DP(i, j, x, dp)), DP(i, j + 1, x, dp));
return ++k;
}
int main() {
while (~scanf("%d", &n) && n) {
memset(s, 0, sizeof s);
memset(d, -1, sizeof d);
memset(u, -1, sizeof u);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + i);
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
int len = (n - i) * 2 + 1;
for (int j = 0; j < len; ++j) {
if (s[i][i + j] == '-') {
if (j & 1) {
ans = max(ans, DP(i, i + j, 1, d));
} else {
ans = max(ans, DP(i, i + j, -1, u));
}
}
}
}
printf("Triangle #%d\n", ++t);
printf("The largest triangle area is %d.\n\n", ans * ans);
}
return 0;
}