Posted on 2010-12-11 20:35
小小菜鸟蛋 阅读(450)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2870这题跟pku2796、2559、3494一样。。。
只可以转为a、b、c三种字母，所以直接枚举，枚举可以转为a的矩阵、b的矩阵、c的矩阵，然后得到每个矩阵的最大矩阵值，再取其中的最大值~~
01 #include <cstdio>
02 #include <cstring>
03 #include <algorithm>
04 using namespace std;
05
06 const int N = 1010;
07 int a[N][N], b[N][N], c[N][N];
08 int n, m;
09 int stack[N], l[N], r[N];
10
11 int max(int x, int y, int z, int u)
12 {
13 return max(max(x, y), max(z, u));
14 }
15
16 int work(int h[])
17 {
18 int top = 0;
19 stack[0] = 0;
20 h[0] = -1;
21 for (int i = 1; i <= n; i++)
22 {
23 while (h[stack[top]] >= h[i])
24 top--;
25 l[i] = i - stack[top] - 1;
26 stack[++top] = i;
27 }
28 top = 0;
29 stack[0] = n + 1;
30 h[n+1] = -1;
31 for (int i = n; i >= 1; i--)
32 {
33 while (h[stack[top]] >= h[i])
34 top--;
35 r[i] = stack[top] - i - 1;
36 stack[++top] = i;
37 }
38 int ans = -1;
39 for (int i = 1; i <= n; i++)
40 ans = max(ans, (r[i] + l[i] + 1) * h[i]);
41
42 return ans;
43 }
44
45 int main()
46 {
47 while (scanf("%d%d", &m, &n) != EOF)
48 {
49 memset(a, 0, sizeof(a));
50 memset(b, 0, sizeof(b));
51 memset(c, 0, sizeof(c));
52 char ch;
53 for (int i = 1; i <= m; i++)
54 {
55 scanf("%c", &ch); //读掉过行符
56 for (int j = 1; j <= n; j++)
57 {
58 scanf("%c", &ch);
59 if (ch == 'w' || ch == 'y' || ch == 'z' || ch == 'a')
60 a[i][j] = a[i-1][j] + 1;
61 if (ch == 'w' || ch == 'x' || ch == 'z' || ch == 'b')
62 b[i][j] = b[i-1][j] + 1;
63 if (ch == 'x' || ch == 'y' || ch == 'z' || ch == 'c')
64 c[i][j] = c[i-1][j] + 1;
65 }
66 }
67 int ans = -1;
68 for (int i = 1; i <= m; i++)
69 ans = max(ans, work(a[i]), work(b[i]), work(c[i]));
70 printf("%d\n", ans);
71 }
72 }