LoveBeyond

POJ 1050 To the Max 解题报告

POJ 2479/POJ 2593的拓展,从一维数组变成了二维矩阵,不过我们可以把情况模拟成一维的情况,在DP的基础上需要加上枚举。
题目要求求出给定的一个矩阵的和最大的子矩阵。
我们可以枚举第a行到第c行的情况(假设已经确定矩阵已经确定为最上面为第a行,最下面为第c行),那么只需要确定列的范围即可。我们可以把每一列都求和,这样会得到单独的一行,就可以直接求这一行的最大子段和即可。
 1 #include <stdio.h>
 2 #include <string.h>
 3  
 4 #define MAX_NUM (100 + 10)
 5  
 6 int main(int argc, char **argv)
 7 {
 8     //freopen("in.txt", "r", stdin);
 9     //freopen("out.txt", "w", stdout);
10  
11     short dic[MAX_NUM][MAX_NUM];
12     short tmp[MAX_NUM];
13     int n, i, j, top, bottom, res, tsum;
14  
15     while (EOF != scanf ("%d", &n))
16     {
17         for (i = 0; i < n; ++i)
18         {
19             for (j = 0; j < n; ++j)
20             {
21                 scanf ("%d", &dic[i][j]);
22             }
23         }
24         res = -99999;
25         for (top = 0; top < n; ++top)
26         {
27             for (bottom = top; bottom < n; ++bottom)
28             {
29                 tsum = 0;
30                 for (i = 0; i < n; ++i)
31                 {
32                     tmp[i] = 0;
33                     for (j = top; j <= bottom; ++j)
34                     {
35                         tmp[i] += dic[j][i];
36                     }
37                     tsum += tmp[i];
38                     if (tsum > res)
39                         res = tsum;
40                     if (tsum < 0)
41                         tsum = 0;
42                 }
43             }
44         }
45         printf ("%d\n", res);
46     }
47  
48     return 0;
49 }

posted on 2011-11-27 17:29 LoveBeyond 阅读(1582) 评论(0)  编辑 收藏 引用

<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

留言簿(1)

文章分类

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

友情链接:C++博客 LoveBeyond 代码疯子 程序人生 C++技术博客