hdu 1081 To The Max

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

题目大意：求一个矩阵之内最大的一个子矩阵的和。子矩阵的和表示的是该矩阵内所有元素的和。

分析：

map[i][j]数组上存的是第i行前j列上的和

第k行上，dp[k][i] = max(dp[k][i-1]+map[k][i],map[k][i])，但是这样只能知道

第k行前i个数的最大和是多少，而不知道是第k行上从第几列到第几列上得来的最

大和。状态转移方程换为，以第k行为终点，从第i列到第j列上的最大和

dp[i][j] = max(map[k][j]-map[k][i-1]+ dp[i][j] ,map[k][j]-map[k][i-1]);

然后用一个Max，求出最大的dp[i][j]。因为不涉及求具体的子矩阵的情况，只需

要得到最优解，那么状态转移方程也可以写成

ans = max( map[k][j]-map[k][i-1]+ ans ,map[k][j]-map[k][i-1] );

ans求的就是是前k行，以第k行为终点，第i到第j列的最大和 

代码1：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 110

using namespace std;

int maps[N][N], dp[N][N];

int main()
{
    int n, i, j, k, a;
    while(~scanf("%d", &n))
    {
        for(i = 1 ; i <= n ; i++)
        {
            for(j = 1 ; j <= n ; j++)
            {
                scanf("%d", &a);
                maps[i][j] = maps[i][j - 1] + a;
            }
        }//maps[i][j]存的是第i行前j列的和
        int Max = -INF;
        for(j = 1 ; j <= n ; j++)
        {
            for(i = 1 ; i <= j ; i++)
            {
                dp[i][j] = 0;
                for(k = 1 ; k <= n ; k++)
                {
                    dp[i][j] = max(maps[k][j] - maps[k][i - 1] + dp[i][j], maps[k][j] - maps[k][i - 1]);
                    if(dp[i][j] > Max)
                        Max = dp[i][j];
                }
            }
        }
        printf("%d
", Max);
    }
    return 0;
}

代码2：

详细请参考：

http://blog.csdn.net/u013611908/article/details/41781431

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 110

using namespace std;

int maps[N][N], dp[N][N];

int main()
{
    int n, i, j, k, a;
    while(~scanf("%d", &n))
    {
        for(i = 1 ; i <= n ; i++)
        {
            dp[i][0] = 0;
            for(j = 1 ; j <= n ; j++)
            {
                scanf("%d", &a);
                maps[i][j] = maps[i][j - 1] + a;
            }
        }//maps[i][j]存的是第i行前j列的和
        int Max = -INF, sum;
        for(i = 1 ; i <= n ; i++)
        {
            for(j = i ; j <= n ; j++)
            {
                sum = 0;
                for(k = 1 ; k <= n ; k++)
                {
                    if(sum < 0)
                        sum = 0;
                    sum += maps[k][j] - maps[k][i - 1];
                    Max = max(Max, sum);
                }
            }
        }
        printf("%d
", Max);
    }
    return 0;
}