题目大意：
https://www.luogu.org/problemnew/show/P1736
题解
dplr[][] 当前点左边（副对角线时为右边）有多少个连续的0
dpup[][] 当前点上边有多少个连续的0
dp[][] 当前点左上有多少个连续的符合要求的1
主对角线时 dp[ i ][ j ]=min(dp[ i-1 ][ j-1 ],min(dplr[ i ][ j-1 ],dpup[ i-1 ][ j ]))+1;
如
原数组 dplr[][] dpup[][] dp[][]
1 0 0 0 1 2 0 1 1 1 0 0
0 1 0 1 0 1 1 0 2 0 2 0
1 0 1 0 1 0 0 1 0 1 0 2
首先 对于一个正方形矩阵来说 其边长上鱼的个数和对角线上鱼的个数是相等的
所以 dp[ i ][ j ] 在 dp[ i-1 ][ j-1 ]、dplr[ i ][ j-1 ]、dp[ i-1 ][ j ] 中取小
相当于查看其 左上的 [i-1][j-1]子矩阵、第i行当前点以左、第j列当前点以上 符合要求的长度
#include <bits/stdc++.h> using namespace std; int n,m,a[2505][2505],dp[2505][2505]; int dplr[2505][2505],dpup[2505][2505]; int main() { while(~scanf("%d%d",&n,&m)) { int ans=0; memset(dp,0,sizeof(dp)); memset(dplr,0,sizeof(dplr)); memset(dpup,0,sizeof(dpup)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { /// 主对角线 scanf("%d",&a[i][j]); if(a[i][j]) dp[i][j]=min(dp[i-1][j-1],min(dplr[i][j-1],dpup[i-1][j]))+1; else { dplr[i][j]=dplr[i][j-1]+1; dpup[i][j]=dpup[i-1][j]+1; } ans=max(ans,dp[i][j]); } memset(dp,0,sizeof(dp)); memset(dplr,0,sizeof(dplr)); memset(dpup,0,sizeof(dpup)); for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) { /// 副对角线 if(a[i][j]) dp[i][j]=min(dp[i-1][j+1],min(dplr[i][j+1],dpup[i-1][j]))+1; else { dplr[i][j]=dplr[i][j+1]+1; dpup[i][j]=dpup[i-1][j]+1; } ans=max(ans,dp[i][j]); } printf("%d\n",ans); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/9333677.html
相关资源：JAVA上百实例源码以及开源项目