poj 1050 To the Max(最大子矩阵之和)

http://poj.org/problem?id=1050

       我们已经知道求最大子段和的dp算法 参考 here  也可参考编程之美有关最大子矩阵和部分。

      然后将这个扩大到二维就是这道题。顺便说一下，有时候不要把问题想复杂了，有些问题只能靠暴力求解，而这道题是暴力加算法。

      在这个题中，我们可以把二维压缩到一维然后求解最大子段。我们先枚举所求矩阵的起点行和结束行，然后把每一列的数据之和求出，用这些数据和就构造出一个一维的数组（代码中我没有明确表示出这个数组），然后用最大子段和的dp算法求解。

     关于二维压缩到一维的过程，适当处理可以大大减小时间复杂度。

     最终时间复杂度是O(n^3)；

我的代码，思路是正确的，但是提交上去之后wa了，求大神赐教。

  

   

    

     

    
    

     

      //2013-06-26-08.45
     
    
   

    

     

    
    

     

      //poj 1050
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      int map[103][103];
     
    
   

    

     

    
    

     

      int sum[103][103];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n;
     
    
   

    

     

    
    

     
    while (cin >> n)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        memset(sum, 0, sizeof(sum));
     
    
   

    

     

    
    

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

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            for (int j = 1; j <= n; j++)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     

                       cin >> map[i][j];
     
    
   

    

     

    
    

     

                       sum[i][j] = map[i][j] + sum[i-1][j];
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        int ans = 0;
     
    
   

    

     

    
    

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

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            for (int j = 0; j < i; j++)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                int tol = 0;
     
    
   

    

     

    
    

     
                for (int k = 1; k <= n; k++)
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     
                    if (sum[i][k]-sum[j][k] < 0)  //这个地方就是压缩后的数组
     
    
   

    

     

    
    

     

                              tol = 0;
     
    
   

    

     

    
    

     
                    else
     
    
   

    

     

    
    

     

                              tol += (sum[i][k]-sum[j][k]);
     
    
   

    

     

    
    

     
                    if (tol > ans)
     
    
   

    

     

    
    

     

                              ans = tol;
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              cout << ans << endl;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/9176155