HDU2830矩阵交换II的高效解法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2830。

此题的核心在于如何有效地处理矩阵中的1，以找到最大可能的矩形面积。为此，我们使用一个辅助数组 h[] 来记录每一列从上到下连续1的数量。

例如，对于矩阵：

1011
1001
0001

我们可以构建如下 h[] 数组：

1011
2002
0003

接下来，由于列数可以变化，我们将每行的所有1向右移动，以便于计算矩形的最大面积。具体步骤如下：

• 对于第一行，有3个1，变为0111，因此 ans = 3*1 + 2*1 + 1*1。
• 对于第二行，有2个1，变为0022，因此 ans = 2*2 + 2*1。
• 对于第三行，有1个1，变为0003，因此 ans = 3*1。

最终选择最大的 ans 值，即为所求的最大矩形面积。

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000 + 5;
int temp[maxn], h[maxn];
char Matrix[maxn][maxn];

int main() {
    int R, C;
    while (scanf("%d%d", &R, &C) != EOF) {
        memset(h, 0, sizeof(h));
        for (int i = 0; i             scanf("%s", Matrix[i]);
        int ans = 0;
        for (int i = 0; i             for (int j = 0; j                 if (Matrix[i][j] == '1') h[j]++;
                else h[j] = 0;
            memcpy(temp, h, sizeof(h));
            sort(temp, temp + C);
            for (int j = 0; j                 ans = max(ans, temp[j] * (C - j));
        }
        cout <    }
    return 0;
}