【二分查找最优解】FZU 2056 最大正方形

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

分析：开始以为是DP或者二维RMQ，其实用二分就可以做出来；

　　　在输入时构造元素和矩阵dp[][]（即dp[i][j]为从(1,1)到(i,j)的矩形范围元素和）;再在(0，min(m,n))范围内二分查找满足条件的最优解H；计算正方形内元素和的方法要掌握;

　　　注意二分时要避免出现L==M而死循环的情况。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn = 1010;
 7 int m, n, lim;
 8 int dp[maxn][maxn];
 9 bool solve(int h)
10 {
11    
12     for(int i = h; i <= n; i++)
13     {
14         for(int j = h; j <= m; j++)
15         {
16             if(dp[i][j]-dp[i-h][j]-dp[i][j-h]+dp[i-h][j-h] > lim) continue;
17             return true;
18         }
19     }
20     return false;
21 }
22 int main()
23 {
24     int T; scanf("%d", &T);
25     while(T--)
26     {
27         scanf("%d%d%d", &n, &m, &lim);
28         memset(dp, 0, sizeof(dp));
29         for(int i = 1; i <= n; i++)
30         {
31             int tmp = 0;
32             for(int j = 1; j <= m; j++)
33             {
34                 int x; scanf("%d", &x);
35                 tmp += x;
36                 dp[i][j] = dp[i-1][j]+tmp;
37             }
38         }
39 
40         int H = min(n, m);
41         int L = 0, R = H;
42         int M;
43         while(L < R)
44         {
45             M = L+(R-L)/2;
46             if(M == L) M++; //避免死循环
47             if(solve(M)) L = M;
48             else R = M-1;
49         }
50         cout << L*L << endl;
51     }
52     return 0;
53 }