首页 > POJ解题报告 > POJ 1050 To the Max[DP]

POJ 1050 To the Max[DP]

POJ 2479/2593的拓展,从一维数组变成了二维矩阵,不过我们可以把情况模拟成一维的情况,在DP的基础上需要加上枚举。
题目要求求出给定的一个矩阵的和最大的子矩阵。
我们可以枚举第a行到第c行的情况(假设已经确定矩阵已经确定为最上面为第a行,最下面为第c行),那么只需要确定列的范围即可。我们可以把每一列都求和,这样会得到单独的一行,就可以直接求这一行的最大子段和即可。
POJ 1050 To the Max[DP] 传送:POJ 1050 To the Max http://poj.org/problem?id=1050

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <string.h>
 
#define MAX_NUM (100 + 10)
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	short dic[MAX_NUM][MAX_NUM];
	short tmp[MAX_NUM];
	int n, i, j, top, bottom, res, tsum;
 
	while (EOF != scanf ("%d", &n))
	{
		for (i = 0; i < n; ++i)
		{
			for (j = 0; j < n; ++j)
			{
				scanf ("%d", &dic[i][j]);
			}
		}
		res = -99999;
		for (top = 0; top < n; ++top)
		{
			for (bottom = top; bottom < n; ++bottom)
			{
				tsum = 0;
				for (i = 0; i < n; ++i)
				{
					tmp[i] = 0;
					for (j = top; j <= bottom; ++j)
					{
						tmp[i] += dic[j][i];
					}
					tsum += tmp[i];
					if (tsum > res)
						res = tsum;
					if (tsum < 0)
						tsum = 0;
				}
			}
		}
		printf ("%d\n", res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 1050 To the Max[DP]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.