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

首先，这题和[P1387 最大正方形](https://www.luogu.org/problemnew/show/P1387)很像，主体思路和[WYS大佬的暴力方向](https://www.luogu.org/blog/WYW-wys/solution-p1387)差不多 我们可以用前缀和处理出各个二维子矩阵的大小，尤其是正方形。 这里二维前缀和用到了容斥原理，相信学过集合的高中同学们应该掌握的差不多了 那么这样可以处理掉在斜率为$-1$的直线上的“鱼”了，我们还需要处理斜率为$1$的直线上的鱼，就可以将矩阵对称过来，用这样一句话： ```cpp c[i][j]=a[i][m-j+1]; ``` 就可以重复做一遍枚举了 最根本的想法是：在一个$n*n$的正方形中，前缀和是$n$，则这个正方形可以被“创意地”吃掉。因此，我们需要向右下角遍历，但这样会平添一些不必要的步骤，所以我们借助DP思想，承接左上角的状态，向下遍历，于是就有了这份**~~90分~~**代码 ```cpp #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$代码 ```cpp #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; } ```