HDU 2830 Matrix Swapping II

浏览数：28 / 时间：2015年06月11日

给一个矩阵，依然是求满足条件的最大子矩阵

不过题目中说任意两列可以交换，这是对题目的简化

求出h数组以后直接排序，然后找出(col-j)*h[j]的最大值即可(这里的j是从0开始)

因为排序会影响到h数组下一行的求解，所以将h数组中的元素复制到temp数组中去，再排序

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 1010;
 9 char map[maxn][maxn];
10 int h[maxn], temp[maxn];
11 
12 int main(void)
13 {
14     #ifdef LOCAL
15         freopen("2830in.txt", "r", stdin);
16     #endif
17 
18     int row, col;
19     while(scanf("%d%d", &row, &col) == 2)
20     {
21         int i, j;
22         for(i = 0; i < row; ++i)
23             scanf("%s", map[i]);
24         memset(h, 0, sizeof(h));
25         int ans = 0;
26         for(i = 0; i < row; ++i)
27         {
28             for(j = 0; j < col; ++j)
29             {
30                 if(map[i][j] == ‘1‘)
31                     ++h[j];
32                 else
33                     h[j] = 0;
34             }
35             memcpy(temp, h, sizeof(h));
36             sort(temp, temp + col);
37             for(j = 0; j < col; ++j)
38                 ans = max(ans, (col-j)*temp[j]);
39         }
40         printf("%d\n", ans);
41     }
42     return 0;
43 }