题解：P14209 [ROI 2016 Day2] 视频监控管理

lzt415 · 2025-10-28 09:02:45 · 题解

思路

既然是行和列的循环，我们套路化的把数组复制一下，即这个矩形的长和宽乘以 2。

然后我们处理二维前缀和，在这个大矩形中找 n\times m 的矩形即可。

代码如下。

code

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,m,a[N][N],b[N][N],sum[N][N];
int main()
{
    freopen("room.in","r",stdin);
    freopen("room.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;cin>>c;
            a[i][j]=a[i+n][j]=a[i][j+m]=a[i+n][j+m]=c-'0';
        }
    }
    for(int i=2;i<=2*n;i++)
    {
        for(int j=2;j<=2*m;j++)
        {
            if(a[i][j]==a[i-1][j]&&a[i][j]==a[i][j-1]&&a[i][j]==a[i-1][j-1]) b[i][j]=1;
            else b[i][j] = 0; 
        }
    }
    for(int i=1;i<=2*n;i++)
    {
        for(int j=1;j<=2*m;j++)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+b[i][j];
        }
    }
    int ans=0;
    for(int i=n+1;i<=2*n;i++)
    {
        for(int j=m+1;j<=2*m;j++)
        {
            int now=sum[i][j]-sum[i-n+1][j]-sum[i][j-m+1]+sum[i-n+1][j-m+1];
            ans=max(ans,now);
        }
    }
    cout<<ans;
    return 0;
}