xindoo is
always here

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 » poj 1050 To the Max(最大子矩阵之和)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏