hdu2830_Matrix Swapping II

Posted on 2010-11-29 14:07 小小菜鸟蛋 阅读(628) 评论(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 }

Feedback

# re: hdu2830_Matrix Swapping II  回复  更多评论   

2011-07-11 14:52 by yaonie
如果数据是
0010
1100
1011
您要怎么解释呢?h[i]分别是多少 0 0 1 0??

# re: hdu2830_Matrix Swapping II  回复  更多评论   

2011-07-11 15:11 by yaonie
了解了 膜拜了

# re: hdu2830_Matrix Swapping II  回复  更多评论   

2012-03-26 12:00 by re
如果是
1111 ->1111
0000 ->0000
1110 ->1110
呢? 您要怎么解释

# re: hdu2830_Matrix Swapping II  回复  更多评论   

2012-03-26 18:16 by 小小菜鸟蛋
@re
得到h[]数组:-> 可以得到的矩阵分别是:
1 1 1 1 -> 1*1 1*2 1*3 1*4 -> 选择最大的1*4
0 0 0 0 -> 0*1 0*2 0*3 0*4
1 1 1 0 -> 1*1 1*2 1*3 0*4
代码37、38行就是在每行处理完后,找出到目前这行为止最大的那个矩阵,放入maxnum中。

# re: hdu2830_Matrix Swapping II  回复  更多评论   

2012-07-29 15:07 by dacainiao
@re求大牛指点思考过程!!!

# re: hdu2830_Matrix Swapping II  回复  更多评论   

2012-08-03 10:50 by 小小菜鸟蛋
@dacainiao
额,请问是哪里看不懂呢?

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理