题解 P1736 【创意吃鱼法】

思路：dp+预处理 这道题其实和P1387 最大正方形很像，只不过多了一个预处理罢了 s1[i][j]表示（i，j）最多向左（或右）延伸多少个格子，使这些格子中的数都是0（不包括（i，j）） s2[i][j]表示（i，j）最多向上延伸多少个格子，使这些格子中的数都是0（不包括（i，j）） f[i][j]表以（i，j）为右下（左下）角的最大对角线长度 方程：f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1; 不懂可以根据这个例子想想 - 1 0 0 - 0 1 0 - 0 0 1 dp两遍，分别对应两条对角线 最后附上~~精简的~~代码 ```cpp #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<map> typedef long long ll; using namespace std; int n,m,ans; int a[2509][2509],f[2509][2509],s1[2509][2509],s2[2509][2509];//s1为横向，s2为纵向 int main() { cin>>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]) { s1[i][j]=s1[i][j-1]+1; s2[i][j]=s2[i-1][j]+1; } if(a[i][j]) f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1; ans=max(ans,f[i][j]); } //第二遍右上——左下 memset(f,0,sizeof(f)); memset(s1,0,sizeof(s1));//数组置0 memset(s2,0,sizeof(s2)); for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) { if(!a[i][j]) { s1[i][j]=s1[i][j+1]+1; s2[i][j]=s2[i-1][j]+1; } if(a[i][j]) f[i][j]=min(f[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1; ans=max(ans,f[i][j]); } cout<<ans<<endl; return 0; } ```