题解 P2706 【巧克力】

Lonely_NewYear · 2021-08-21 19:41:58 · 题解

P2706 题解

题目分析

观察这题的数据范围可以知道大概 O(n^3) 的复杂度就可以通过本题，所以可以暴力一点，枚举一下最终选出的矩形巧克力的右下角以及右上角（枚举右下角 O(n^2)，再枚举右上角只需要从右下角往上一直枚举到第 1 行，所以是 O(n)，一起就是 O(n^3)）,同时计算答案。

具体如何计算呢？因为我们要求的是巧克力最多的那个矩形，所以只要矩形左边界旁没有 0 就可以继续把左边界往左推。可以维护一个变量 l 表示矩形的左边界，如果 f_{i,j} 表示 a_{i,j} 左边最近的 0 的位置，那么显然 l=max(l,f_{i,j}+1)（再往左就碰到 0 了）。此时矩形的右上角，右下角，左边界都确定了，那么就可以确定这个矩形，就可以利用二维前缀和计算矩形内的巧克力数量。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int a[301][301],f[301][301],s[301][301];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j])f[i][j]=f[i][j-1];
            else f[i][j]=j;
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int l=0;
            for(int k=i;k>=1;k--)
            {
                if(!a[k][j])break;
                l=max(l,f[k][j]);
                ans=max(ans,s[i][j]-s[i][l]-s[k-1][j]+s[k-1][l]);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

谢谢观看！