题解 P1736 【创意吃鱼法】 暴力枚举做法

· · 题解

首先，这题和P1387 最大正方形很像，主体思路和WYS大佬的暴力方向差不多

我们可以用前缀和处理出各个二维子矩阵的大小，尤其是正方形。

这里二维前缀和用到了容斥原理，相信学过集合的高中同学们应该掌握的差不多了

那么这样可以处理掉在斜率为-1的直线上的“鱼”了，我们还需要处理斜率为1的直线上的鱼，就可以将矩阵对称过来，用这样一句话：

c[i][j]=a[i][m-j+1];

就可以重复做一遍枚举了 最根本的想法是：在一个n*n的正方形中，前缀和是n，则这个正方形可以被“创意地”吃掉。因此，我们需要向右下角遍历，但这样会平添一些不必要的步骤，所以我们借助DP思想，承接左上角的状态，向下遍历，于是就有了这份90分代码

#include<cstdio>
#include<cstring>
int a[2501][2501];//正向矩阵
int b[2501][2501];//正向前缀和
int f[2501][2501];//dp用数组
int c[2501][2501];//镜像矩阵
int d[2501][2501];//镜像前缀和
int turn1(int x1,int y1,int x2,int y2)//处理二维前缀和
{
    return b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1];
}
int turn2(int x1,int y1,int x2,int y2)
{
    return d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1];
}
int main()
{
    memset(b,0,sizeof(b));
    memset(f,0,sizeof(f));
    int n,m,maxx=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            c[i][j]=a[i][m-j+1];
            d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+c[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1&&turn1(i-f[i-1][j-1],j-f[i-1][j-1],i,j)==f[i-1][j-1]+1)
            //问题出现在这里，如果半途终止，那么也不能用到之前的状态，但实际上是有之前的状态的，见hack数据
                f[i][j]=f[i-1][j-1]+1;
            if(f[i][j]>maxx)
                maxx=f[i][j];
        }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(c[i][j]==1&&turn2(i-f[i-1][j-1],j-f[i-1][j-1],i,j)==f[i-1][j-1]+1)
            //同上
                f[i][j]=f[i-1][j-1]+1;
            if(f[i][j]>maxx)
                maxx=f[i][j];
        }
    printf("%d\n",maxx);
    return 0;
}

8 8
1 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1

它为什么90分呢，是它可以被这样的一组数据hack掉，这个程序在承接不了左上角的最大DP正方形边长a时，会自动退回1，而不是从a到1之间找最大的合适的正方形，这样一来，在图中(3,3)点时，f[3][3]就被重置为零，因此解法有问题 这里好像可以二分，但是感觉优化不大，毕竟常数是种信仰，最好还是优化一下，有2500的数据呢，虽然我没有这样做

那么下面贴AC代码

#include<cstdio>
#include<cstring>
int a[2501][2501];//正向矩阵
int b[2501][2501];//正向前缀和
int f[2501][2501];//dp用数组
int c[2501][2501];//镜像矩阵
int d[2501][2501];//镜像前缀和
int turn1(int x1,int y1,int x2,int y2)//二位前缀和处理
{
    return b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1];
}
int turn2(int x1,int y1,int x2,int y2)
{
    return d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1];
}
int main()
{
    memset(b,0,sizeof(b));
    memset(f,0,sizeof(f));
    int n,m,maxx=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
        }
    for(int i=1;i<=n;i++)//处理镜像矩阵
        for(int j=1;j<=m;j++)
        {
            c[i][j]=a[i][m-j+1];
            d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+c[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)//正向枚举
        {
            if(a[i][j]==1)
            {
                f[i][j]=f[i-1][j-1]+1;//这里是可能出现的最大值
                while(turn1(i-f[i][j]+1,j-f[i][j]+1,i,j)!=f[i][j])//判断此时的值能否成立
                    f[i][j]--;//此处是可以二分的
            }
            if(f[i][j]>maxx)
                maxx=f[i][j];
        }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)//镜像枚举（相当于已经处理过）
        {
            if(c[i][j]==1)
            {
                f[i][j]=f[i-1][j-1]+1;
                while(turn2(i-f[i][j]+1,j-f[i][j]+1,i,j)!=f[i][j])
                    f[i][j]--;
            }
            if(f[i][j]>maxx)
                maxx=f[i][j];
        }
    printf("%d\n",maxx);
    return 0;
}