问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2479http://acm.pku.edu.cn/JudgeOnline/problem?id=2593http://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>t ? 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, 0, sizeof(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>t ? max : t;
28 memset(temp, 0, sizeof(int)*col);
29 }
30 }
31 return max;
32 }