首页 > 代码库 > HDU 2830 Matrix Swapping II

HDU 2830 Matrix Swapping II

2024-07-14 18:34:13   220人阅读

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

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

求出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 LOCAL15         freopen("2830in.txt", "r", stdin);16     #endif17 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                 else33                     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 }
代码君

 


联系
我们