原题链接：https://www.luogu.org/problem/show?pid=1387

 

理论上来说可以暴力枚举边长和右下角坐标，而且似乎有人能用这方法过这道题。。。

不过枚举太不现实，而且数据强一点的话就彻底没办法了，还是要DP。

用两个数组l,w分别存储每个位置（包括本身）向左和向上各有几个连续的1，如果一个位置是1，这个位置的w和l就能从别的位置转移过来。（似乎预处理能与输入一起完成？不过我没这么做。）

然后对f数组进行处理，对于每一个正方形，我们都可以把它看作是一层一层的，像这样：

第一层：

1

第二层：

0 1

1 1

第三层：

0 0 1

0 0 1

1 1 1

如果能构成正方形，那么前面的几层都必须是完整的。对于每一个a[i][j]==1的位置，f[i][j]的取值为f[i-1][j-1]+1,l[i][j]与w[i][j]的最小值

插一句，luogu上数据略水，处理f的时候把m写成n居然都有90分。。。

 

#include
     
      void read(int &y){    y=0;char x=getchar();    while(x<'0'||x>'9') x=getchar();    while(x>='0'&&x<='9')    {        y=y*10+x-'0';        x=getchar();    }}int n,m,a[105][105],ans;int f[105][105],l[105][105],w[105][105];int min(int x,int y){    if(x