~~DP?不是前缀和吗~~
by Jianuo_Zhu @ 2018-11-18 16:59:45
@[Jianuo_Zhu](/space/show?uid=30066) 一开始写的前缀和，然后感觉有点暴力 _qwq_
by qsmoonzh @ 2018-11-18 17:02:56
前缀和代码
复杂度O(nm+ans)?
如果是，那和DP没啥区别了
```
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,a[105][105],q[105][105],ans;
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]),q[i][j]=q[i-1][j]+q[i][j-1]-q[i-1][j-1]+a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=ans+1;1;k++) {
if(i-k+1==0||j-k+1==0) break;
if(q[i][j]-q[i-k][j]-q[i][j-k]+q[i-k][j-k]==k*k) ans=k;
else break;
}
printf("%d",ans);
return 0;
}
```
by qsmoonzh @ 2018-11-18 17:05:11
只是不明白DP为什么错了 _qwq_
by qsmoonzh @ 2018-11-18 17:05:43
```cpp
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
using namespace std;
int a[101][101],b,c,d,e,f[101][101],g;
main(){
scanf("%d%d",&b,&c);
for(e=1;e<=b;++e)
for(g=1;g<=c;++g){
scanf("%d",&a[e][g]);
if(a[e][g]==1)f[e][g]=min(min(f[e][g-1],f[e-1][g]),f[e-1][g-1])+1;
d=max(d,f[e][g]);}
printf("%d",d);}
```
by 你打野 @ 2018-11-18 17:21:20
@[朱宇曦](/space/show?uid=113873) 哇神奇，还能这样，受教了orz
by qsmoonzh @ 2018-11-18 23:03:04
@[qsmoonzh](/space/show?uid=96546)
(^_^)
by 你打野 @ 2018-11-19 11:50:18
知道哪里错了，有的转态没更新qwq
by qsmoonzh @ 2018-11-19 22:55:22
此贴完结qwq
by qsmoonzh @ 2018-11-19 22:55:39
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int k;
int a[101][101];
int maxx;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&k);
if(k)
{
a[i][j]=min(a[i-1][j],min(a[i-1][j-1],a[i][j-1]))+1;
}
if(a[i][j]>maxx)
{
maxx=a[i][j];
}
}
}
printf("%d\n",maxx);
return 0;
}
by nobalei @ 2019-03-11 20:51:08