首页 > 代码库 > HDU 2830 Matrix Swapping II
HDU 2830 Matrix Swapping II
给一个矩阵,依然是求满足条件的最大子矩阵
不过题目中说任意两列可以交换,这是对题目的简化
求出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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。