To The Max

showproblem.php?pid=1081

Mean:

求N*N数字矩阵的最大子矩阵和。

analyse:

乍看题目意思很简单，但对于刚开始学DP的新手来说也不是很简单。

这道题使用到的算法是：预处理+最大连续子串和

如果会做最大连续子串和，那么理解这题就相对简单一些，若不知道最大连续子串和，建议先看一下这两题：

http://acm.hdu.edu.cn/showproblem.php?pid=1003

http://acm.hdu.edu.cn/showproblem.php?pid=1231

这题的思想是求最大连续子串和的思想，不过这题是2维的，我们的可以将它转换为一维，然后再运用该思想求它的最大值！

如何将其转化为一维的呢？这就用到了矩阵压缩。

子矩阵必定也是由行和列组成，如上这个矩阵，它的行的组合有 1,1-2,1-3,1-4，2,2-3,2-4，3，3-4,4，无非这10种组合，这样，我们就可以将行进行压缩，比如说：1-2，我们将1,2行数据进行压缩，及进行合并。

0 -2 -7 0
+9 2 -6 2
-------------

9 0 -13 2

那么这样我们就可以通过求最大连续子串和的思想求其最大值，为9

再看：2-4这个组合

9 2 -6 2
-4 1 -4 1
+ -1 8 0 -2

----------------

4 11 -10 1

所以它的最大和为15

这样通过压缩行，即将这个矩形的宽变为1，可以迅速的求出子矩阵的值，并求出最大值，因为求最大连续子串和思想是线性的，复杂度为O(N)，所以可以快速求出压缩后矩阵的和！

下面是自己写的代码：（虽然有点暴力，但是过这题时间毫无压力）

Time complexity: O(N*N)

Source code:

/*

* this code is made by crazyacking

* Verdict: Accepted

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-);

int dp[][];

int map[][];

int main()

{

      int i,j,n,i1,i2,sum,temp,mx,res;

      while(scanf("%d",&n)!=EOF)

      {

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

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

                        scanf("%d",&map[i][j]);

            memset(dp,,sizeof(dp));

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

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

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

            res=;

            for(i1=; i1<=n; i1++)

                  for(i2=i1; i2<=n; i2++)

                  {

                        mx=sum=;

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

                        {

                              sum+=dp[j][i2]-dp[j][i1-];

                              if(sum>=)

                              {

                                    if(sum>=mx) mx=sum;

                              }

                              else sum=;

                        }

                        if(mx>=res) res=mx;

                  }

            printf("%d\n",res);

      }

      return ;

}

巴特西

dp - 最大子矩阵和 - HDU 1081 To The Max

To The Max

Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=1081

最新文章

热门文章