Posted on 2010-11-29 14:07
小小菜鸟蛋 阅读(649)
评论(7) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2830
O（n*mlg m）：
用h[ i ]表示在该行第 i 列以a[ i ]结尾的连续“1” 的长度：若a[i]为“1”，则h[i] = h[i-1] + 1；若a[i]为“0”，则h[i] = 0。。。
以样例1为例：
h[1] h[2] h[3] h[4]
1011 1 0 1 1
1001 2 0 0 2
0001 0 0 0 3
一边读入a[i]一边处理h[i]，读完一行就处理一次，计算保存到当前行的最大“1” 矩阵。。。
因为任意两列可任意对调，所以得到的h[]从大到小排序一下，h[i] * i 即是到这一列为止最大的矩阵。。
例，某行读完后h[]为3 2 1，即
1 0 0
1 1 0
1 1 1
可以组成的矩阵有：3*1，2*2，1*3
最大矩阵是：2*2
若读完后h[]为3 1 2，则要排序使之变为3 2 1 。。
01 #include <cstdio>
02 #include <cstring>
03 #include <algorithm>
04 using namespace std;
05
06 const int N = 1010;
07 char a[N];
08 int h[N], k[N];
09
10 bool comp(int a, int b)
11 {
12 return a > b;
13 }
14
15 int main()
16 {
17 int n, m;
18 while (scanf("%d%d", &n, &m) != EOF)
19 {
20 memset(h, 0, sizeof(h));
21 int maxnum = 0;
22 for (int i = 1; i <= n; i++)
23 {
24 char ch;
25 scanf("%c", &ch); //读掉前一行行尾的过行号
26 for (int j = 1; j <= m; j++)
27 {
28 scanf("%c", &a[j]);
29 if (a[j] == '1')
30 h[j]++;
31 else h[j] = 0;
32 }
33 for (int j = 1; j <= m; j++) //要另开一个数组排序，这样才不会影响下一行h[]的计算
34 k[j] = h[j];
35
36 sort(k + 1, k + m + 1, comp);
37 for (int j = 1; j <= m; j++)
38 maxnum = maxnum > (k[j]*j) ? maxnum : (k[j]*j);
39 }
40 printf("%d\n", maxnum);
41 }
42 }