A Za, A Za, Fighting...

坚信:勤能补拙

PKU 2479 Maximum sum/2593 Max Sequence/1050 To the Max

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2479
http://acm.pku.edu.cn/JudgeOnline/problem?id=2593
http://acm.pku.edu.cn/JudgeOnline/problem?id=1050

思路:
基础: 最大子段和问题
给定N个整数(可能为负)组成的序列a1, a2, a3, ..., aN,求子段ai, a(i+1), ... , aj的和的最大值
非常典型的动态规划,状态迁移方程:
      f(i) = max(ai, f[i-1]+ai), f(i)表示以ai结尾的最大子段和
据此我们可以得到O(n)的求解算法

PKU 2479与2593这两题其实是同一个问题(买一送一),都是上述最大子段和问题的变形
一样非常自然的想法是枚举所有可能的"分开点", 然后分别计算前后两个子数组的最大子段和,不过如果依次枚举的话是会超时的
这时候就需要利用对于上述f(i)表达式的理解了, 我们可以依次从头到尾、从尾到头扫描两次原数组,并把相应的最大子段和分别保存起来,称为hd[i]和tl[i], 这里注意f(i)并非是最大子段和
假设现在枚举到分开点t, 那么a[0..t]的最大子段和可以通过hd[i]获得,a[t+1...len]的最大子段和则可以通过tl[i]获得
 1 /*
 2  * hd[i] stores the maximum sub-segment from arr[0..i]
 3  * tl[i] stores the maximum sub_segment from arr[i+1..n-1]
 4  */
 5 long *hd, *tl;
 6 
 7 long
 8 max_subsum(int *arr, long N)
 9 {
10     long i, temp, max;
11     /* hd */
12     hd[0= max = arr[0];
13     for(i=1; i<N; i++) {
14         temp = hd[i-1+ arr[i];
15         hd[i] = temp>arr[i] ? temp : arr[i];
16     }
17     for(i=1; i<N; i++) {
18         hd[i] = hd[i] > max ? hd[i] : max;
19         max = hd[i];
20     }
21     /* tl */
22     tl[N-1= max = arr[N-1];
23     for(i=N-2; i>=0; i--) {
24         temp = tl[i+1+ arr[i];
25         tl[i] = temp>arr[i] ? temp : arr[i];
26     }
27     for(i=N-2; i>=0; i--) {
28         tl[i] = tl[i] > max ? tl[i] : max;
29         max = tl[i];
30     }
31 }
32 
33 long
34 enumerate()
35 {
36     long i, temp, max = hd[0+ tl[1];
37     for(i=1; i<n-1; i++) {
38         temp = hd[i] + tl[i+1];
39         max = max>temp ? max : temp;
40     }
41     return max;
42 }

PKU 1050是一道"隐藏"地比较深的最大子段和问题,之所以说它隐藏的比较深,是因为题目要求的是求最大子矩阵问题
上网搜了别人的思路,才发现这题是可以转化成求最大子段和问题的:只要将矩阵的行或者列合并即可
不得不感叹这思路的精妙啊呵呵
 1 int
 2 max_subsum(int *arr, int N)
 3 {
 4     int i, t, max;
 5     max = t = arr[0];
 6     for(i=1; i<N; i++) {
 7         t = t+arr[i]>arr[i] ? t+arr[i] : arr[i];
 8         max = max>? max : t;
 9     }
10     return max;
11 }
12 
13 int 
14 enumerate()
15 {
16     int t, max = 0;
17     int i, j, k, len, temp[col];
18     memset(temp, 0sizeof(int)*col);
19     for(len=1; len<=row; len++) {
20         for(i=0; i<row; i++) {
21             for(j=i; j<len; j++) {
22                 for(k=0; k<col; k++) {
23                     temp[k] += arr[j][k];
24                 }
25             }
26             t = max_subsum(temp, col);
27             max = max>? max : t;
28             memset(temp, 0sizeof(int)*col);
29         }
30     }
31     return max;
32 }

posted on 2010-06-29 16:48 simplyzhao 阅读(283) 评论(0)  编辑 收藏 引用 所属分类: C_动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜