这道题目可以二分
求出二维前缀和，枚举每一个顶点，然后二分正方形边长，显然具有单调性，时间复杂度为\(O(n^2logn)\)
如果\(n\)为\(5000\)怎么办？
这个时候要用到DP
说明一下正确性
假设我们的\(min\)取的是\(f[i-1][j]\)，如下
那么对当前这个顶点的正方形就是
由于\(f[i-1][j]≤f[i-1][j-1]\)，那么说明红色那一列全部都是\(1\)
由于\(f[i-1][j]≤f[i][j-1]\)，那么说明棕色那一行全部都是\(1\)
所以我们取的矩阵是合理的。但是如果更大，比如紫色那一个
肯定就是不行的，因为如果可以的话，就说明\(f[i-1][j]\)可以多\(1\)了
标签：二分,别墅,全部都是,说明,正方形,顶点 From： https://www.cnblogs.com/dingxingdi/p/17972730