题解：P10719 [GESP202406 五级] 黑白格

Vct14 · 2024-07-09 14:58:24 · 题解

简单前缀和模板题。题目可以转化为元素和大于等于 k 的最小子矩阵中的元素个数。我们处理出矩阵的前缀和，然后暴力枚举子矩阵的左上和右下端点，若当前矩阵中元素和大于等于 k，则更新最小值。记得判不存在的情况。

#include<bits/stdc++.h>
using namespace std;

const int N=102;
int a[N][N];
int s[N][N];

int main(){
    int n,m,k;cin>>n>>m>>k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;cin>>c;
            a[i][j]=c-'0';
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    int mn=INT_MAX;
    for(int i1=1; i1<=n; i1++) for(int j1=1; j1<=m; j1++) for(int i2=i1; i2<=n; i2++) for(int j2=j1; j2<=m; j2++) if(s[i2][j2]-s[i1-1][j2]-s[i2][j1-1]+s[i1-1][j1-1]>=k) mn=min(mn,(i2-i1+1)*(j2-j1+1));
    if(mn!=INT_MAX) cout<<mn;
    else cout<<0;
    return 0;
}

附一份官方题解。