【二分查找最优解】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而死循环的情况。

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 using namespace std;

 const int maxn = ;

 int m, n, lim;

 int dp[maxn][maxn];

 bool solve(int h)

 {

     for(int i = h; i <= n; i++)

     {

         for(int j = h; j <= m; j++)

         {

             if(dp[i][j]-dp[i-h][j]-dp[i][j-h]+dp[i-h][j-h] > lim) continue;

             return true;

         }

     }

     return false;

 }

 int main()

 {

     int T; scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d%d", &n, &m, &lim);

         memset(dp, , sizeof(dp));

         for(int i = ; i <= n; i++)

         {

             int tmp = ;

             for(int j = ; j <= m; j++)

             {

                 int x; scanf("%d", &x);

                 tmp += x;

                 dp[i][j] = dp[i-][j]+tmp;

             }

         }

         int H = min(n, m);

         int L = , R = H;

         int M;

         while(L < R)

         {

             M = L+(R-L)/;

             if(M == L) M++; //避免死循环

             if(solve(M)) L = M;

             else R = M-;

         }

         cout << L*L << endl;

     }

     return ;

 }

巴特西

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

最新文章

热门文章