HDU 2830 Matrix Swapping II

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

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

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

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

 //#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
char map[maxn][maxn];
int h[maxn], temp[maxn]; int main(void)
{
#ifdef LOCAL
freopen("2830in.txt", "r", stdin);
#endif int row, col;
while(scanf("%d%d", &row, &col) == )
{
int i, j;
for(i = ; i < row; ++i)
scanf("%s", map[i]);
memset(h, , sizeof(h));
int ans = ;
for(i = ; i < row; ++i)
{
for(j = ; j < col; ++j)
{
if(map[i][j] == '')
++h[j];
else
h[j] = ;
}
memcpy(temp, h, sizeof(h));
sort(temp, temp + col);
for(j = ; j < col; ++j)
ans = max(ans, (col-j)*temp[j]);
}
printf("%d\n", ans);
}
return ;
}

代码君

上一篇:NOIP2018提高组Day2 解题报告


下一篇:uboot(二): Uboot-arm-start.s分析