#### FZU 2056 – 最大正方形 [二分+递推]

vjudge链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=29392

Description

Input

0 < n <= 1000, 0 < m <= 1000, 0 <= limit <=100000000 0 <= A[i] <= 1000

Output

福州月赛题，算是一套题中的中档题，当时想到了二分找边，但没想到怎么来求面积，想动规求但是总复杂度是o(n^3 logn)的方法，就没写。今天重新看了下学长的代码，终于知道了递推求面积的方法，总复杂度是o(n^2 logn)。最后自己做居然卡在二分上了，不太爽。

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1024;
int n, m, limit;
int a[maxn][maxn], s[maxn][maxn];

bool can(const int h){
for(int i = h; i <= n; ++i)
for(int j = h; j <= m; ++j){
int t = s[i][j] - s[i-h][j] - s[i][j-h] + s[i-h][j-h];
if(t <= limit) return true;
}
return false;
}
int main(){
int T; scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &m, &limit);
memset(a, 0, sizeof(a)); memset(s, 0, sizeof(s));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
scanf("%d", &a[i][j]);
s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}
int l = 0, r = min(n, m);
while(l < r){
int mid = l + (r - l) / 2;
if(mid == l) ++mid;
if(can(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", l * l);
}
return 0;
}