Posted on 2010-12-07 15:19
小小菜鸟蛋 阅读(328)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://poj.org/problem?id=3494像hdu2830那样处理矩阵，每一行保存的值是第 i 列以a[i]结尾的连续1的高度。。
（http://www.cppblog.com/A-wu/archive/2010/11/29/134980.html）
然后每一行就像pku2559和pku2796那样处理，得到每一行的最大区间值；再通过枚举 m 行得到整个矩阵的最大值。。注意：这道题的l[]和r[]存放的不是左右边界的下标，而是h[i]到其左右边界的个数。
01 #include <cstdio>
02 #include <cstring>
03 #include <algorithm>
04 using namespace std;
05
06 const int N = 2010;
07 int stack[N], l[N], r[N], g[N][N];
08 int n, m;
09
10 int work(int h[])
11 {
12 //求左边界
13 int top = 0;
14 stack[0] = 0;
15 h[0] = -1;
16 for (int i = 1; i <= n; i++)
17 {
18 while (h[stack[top]] >= h[i])
19 top--;
20 l[i] = i - stack[top] - 1;
21 stack[++top] = i;
22 }
23 //求右边界
24 top = 0;
25 stack[0] = n + 1;
26 h[n+1] = -1;
27 for (int i = n; i >= 1; i--)
28 {
29 while (h[stack[top]] >= h[i])
30 top--;
31 r[i] = stack[top] - i - 1;
32 stack[++top] = i;
33 }
34 int ans = -1;
35 for (int i = 1; i <= n; i++)
36 ans = max(ans, (l[i]+r[i]+1) * h[i]);
37
38 return ans;
39 }
40
41 int main()
42 {
43 while (scanf("%d%d", &m, &n) != EOF)
44 {
45 memset(g, 0, sizeof(g));
46 for (int i = 1; i <= m; i++)
47 for (int j = 1; j <= n; j++)
48 {
49 scanf("%d", &g[i][j]);
50 if (g[i][j] == 1)
51 g[i][j] += g[i-1][j];
52 }
53 int ans = -1;
54 for (int i = 1; i <= m; i++)
55 ans = max(ans, work(g[i]));
56 printf("%d\n", ans);
57 }
58 }