见题:
很水的一题, 数据范围太小, 前缀和加爆搜就行.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=110;
- int ans=1,m,n,sum[maxn][maxn];
- inline int read()
- {
- int x=0,ff=1;
- char ch=getchar();
- while(!isdigit(ch))
- {
- if(ch=='-') ff=-1;
- ch=getchar();
- }
- while(isdigit(ch))
- {
- x=(x<<1)+(x<<3)+(ch^48);
- ch=getchar();
- }
- return x*ff;
- }
- inline void put(int x)
- {
- if(x<0) putchar('-'),x=-x;
- if(x>9) put(x/10);
- putchar(x%10+'0');
- }
- int main()
- {
- //freopen("1.in","r",stdin);
- n=read();m=read();
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- int x=read();
- sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
- }
- }
- for(int len=2;len<=min(n,m);len++)
- {
- int he=len*len;
- for(int x1=1;x1<=n-len+1;x1++)
- {
- for(int y1=1;y1<=m-len+1;y1++)
- {
- int x2=x1+len-1;
- int y2=y1+len-1;
- if((sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1])==he) ans=len;
- }
- }
- }
- put(ans);
- return 0;
- }
可是还是想写正解, DP;
对于这类的二维 DP, 个人理解就是如果保存的从起点到终点的状态会被一些情况所中断, 就要只考虑最下角的点所保存的点的状态, 例如此题, 我们可以保存以 (i,j) 为右下角的状态, 以 f[i][j]保存以 (i,j) 为最右下角的最大正方形边长. 状态转移怎么样呢?
这是我们我们可以轻易的想起二维的前缀和: f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j], 那这个能否用前缀和处理呢, 见下图:
最右下的小矩阵代表 (i,j) 可以很清楚地看出由左边的点, 上边的点, 左上角的点三个点的最小矩阵构成以个完整的矩阵, 即: if(a[i][j]==1) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
这也提醒我们 min 的意义就是几个状态都具备的共同元素.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=110;
- int m,n,a[maxn][maxn],f[maxn][maxn],ans;
- inline int read()
- {
- int x=0,ff=1;
- char ch=getchar();
- while(!isdigit(ch))
- {
- if(ch=='-') ff=-1;
- ch=getchar();
- }
- while(isdigit(ch))
- {
- x=(x<<1)+(x<<3)+(ch^48);
- ch=getchar();
- }
- return x*ff;
- }
- int put(int x)
- {
- if(x<0) putchar('-'),x=-x;
- if(x>9) put(x/10);
- putchar(x%10+'0');
- }
- inline void DP()
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- if(a[i][j]==1) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
- ans=max(ans,f[i][j]);
- }
- }
- }
- int main()
- {
- freopen("1.in","r",stdin);
- n=read();m=read();
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++) a[i][j]=read();
- }
- DP();
- put(ans);
- return 0;
- }
最大矩阵(简单 DP)
来源: http://www.bubuko.com/infodetail-3031803.html