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

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

Description
现在有一个n*m的矩阵A,在A中找一个H*H的正方形,使得其面积最大且该正方形元素的和不大于 limit。

Input
第一行一个整数T,表示有T组数据。
每组数据 第一行三个非负整数 n m limit
接着 n 行,每行 m 个整数。
0 < n <= 1000, 0 < m <= 1000, 0 <= limit <=100000000 0 <= A[i] <= 1000

Output
对于每组数据,输出H*H。
 

 福州月赛题,算是一套题中的中档题,当时想到了二分找边,但没想到怎么来求面积,想动规求但是总复杂度是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;
}

 

欢迎留言