BZOJ 1057: ZJOI 2007 棋盤制作 - DP + 懸線法求最大子矩陣

問題描述

給定 0/1 矩陣，求最大面積的正方形和矩形，要求任意相鄰格子顏色不同（即棋盤染色）。

關鍵轉換

將所有 (i+j)&1 位置的值異或 1，問題轉化為：尋找全 0 或全 1 的最大正方形/矩形。

正方形：DP

f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1（若該格為 1）。對 0 和 1 分別跑一次，取最大邊長平方。

矩形：懸線法 / 單調棧

對每行計算向左/向右連續 1 的長度 L[i][j], R[i][j]，向上高度 H[i][j]。轉移時取寬度最小值：L[i][j] = min(L[i][j], L[i-1][j])，同理 R。面積 = (L+R-1) * (H+1)。對 0 和 1 各跑一次取最大值。

代碼結構

// 正方形 DP
// 矩形懸線法
for (int i=1; i<=m; ++i) {
    for (int j=1; j<=n; ++j) L[i][j] = a[i][j] ? L[i][j-1]+1 : 0;
    for (int j=n; j>=1; --j) R[i][j] = a[i][j] ? R[i][j+1]+1 : 0;
}
for (int i=1; i<=m; ++i)
    for (int j=1; j<=n; ++j)
        if (a[i][j] && a[i-1][j]) {
            H[i][j] = H[i-1][j]+1;
            L[i][j] = min(L[i][j], L[i-1][j]);
            R[i][j] = min(R[i][j], R[i-1][j]);
            ans = max(ans, (L[i][j]+R[i][j]-1)*(H[i][j]+1));
        }