HDU 2830 Matrix Swapping II：列交換後最大全 1 子矩陣面積

題目簡介

給定一個 N × M 的 0/1 矩陣，可以任意交換列。交換後，求由 1 組成的最大子矩陣面積（即「goodness」）。多組測試資料，N, M ≤ 1000。

題目連結：HDU 2830

解題思路

1. 預處理高度：對每個位置 (i, j) 計算向下連續 1 的個數 cnt[i][j]。從最後一行向上遞推：若 s[i][j]=='1' 則 cnt[i][j] = cnt[i+1][j] + 1，否則為 0。
2. 每行排序：對每一行的 cnt[i][*] 從大到小排序。因為列可以任意交換，排序後第 j 大的高度對應寬度為 j 的矩形。
3. 枚舉計算面積：對每一行 i，枚舉 j 從 1 到 M，面積 = j * cnt[i][j]，取最大值作為該行的最大面積 dp[i]。最終答案為所有行的最大值。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 1005;
char s[MAX][MAX];
int cnt[MAX][MAX], dp[MAX];
int n, m;

bool cmp(int a, int b) { return a > b; }

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(cnt, 0, sizeof(cnt));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
        for (int i = n; i >= 1; i--)
            for (int j = 1; j <= m; j++)
                if (s[i][j] - '0') cnt[i][j] = cnt[i+1][j] + 1;
        for (int i = 1; i <= n; i++) {
            sort(cnt[i] + 1, cnt[i] + 1 + m, cmp);
            for (int j = 1; j <= m; j++)
                if (cnt[i][j]) dp[i] = max(dp[i], j * cnt[i][j]);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

時間複雜度 O(N × M log M)，空間複雜度 O(N × M)，適合 N, M ≤ 1000。