G4019 [GESP202509 四级] 排兵布阵 题解

知识点：二维枚举、前缀和、最大矩形。

解题思路

枚举上边界，逐步下扩下边界，用v[j]标记这一列在当前行区间是否全为1。扫描v中连续1的长度，更新高度乘宽度。

为什么正确

全1矩形等价于某行区间内一段连续的全1列，枚举所有高度区间并取最长连续段覆盖最优矩形。

易错点

每次更换上边界都要重新初始化列标记为1；出现0后连续宽度清零。

复杂度

时间O(n²m)，空间O(nm+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>a(n,vector<int>(m));
    for(auto &row:a)for(int &x:row)cin>>x;
    int ans=0;
    for(int x=0;x<n;x++) {
        vector<int>v(m,1);
        for(int y=x;y<n;y++) {
            int streak=0;
            for(int j=0;j<m;j++) {
                v[j]&=a[y][j];
                streak=v[j]?streak+1:0;
                ans=max(ans,streak*(y-x+1));
            }
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。