题目地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1074
这道题的dP是基于 “最大子段和” 的dp方法
例如求数组 1 2 -3 4；-5 6 -1 8 的最大子矩阵和，可以把两行相加得到数组-4 8 -4 12，对这个数组求最大子段和为8+-4+12=16，所以矩阵对应的最大子矩阵为2 -3 4； 6 -1 8
那么可以利用以上思想，对于m*n的矩阵A，选取他的第 i 行到第 j 行的数据组成子矩阵Aij (j-i+1行n列)，Aij 对应的最大子段和可以如下求得：对每一列的值进行累加得到一个一维数组(1*n)，对该数组求最大字段和（ 其中 1=< i=<j<=m ）。
综上所述，A的最大子矩阵和为：max（ subMatrix(Aij) ） ，其中1=< i=<j<=m ，subSegment(Aij) 表示Aij 对应的最大子段和。
上代码：
1
#include<iostream>
2
#include <cstring>
3
using
namespace
std;
4
5
int
maxSubSegment(
int
*arr,
int
n)
6
{
7
int
max=-
65535
,sum=
0
;
8
for
(
int
i=
1
;i<=n;i++
)
9
{
10
if
(sum>
0
)sum+=
arr[i];
11
else
sum=
arr[i];
12
if
(max<sum)max=
sum;
13
}
14
return
max;
15
}
16
17
int
matrix[
101
][
101
];
18
int
sum[
101
];
19
int
main()
20
{
21
int
N;
22
cin>>
N;
23
24
for
(
int
i=
1
;i<=N;i++
)
25
for
(
int
j=
1
;j<=N;j++
)
26
{
27
cin>>
matrix[i][j];
28
}
29
////////////////////////
//Dp;
30
int
result=-
65535
;
31
for
(
int
i=
1
;i<=N;i++
)
32
{
33
memset(sum,
0
,
sizeof
(sum));
34
for
(
int
j=i;j<=N;j++
)
35
{
36
for
(
int
k=
1
;k<=N;k++
)
37
sum[k]+=
matrix[j][k];
38
int
re=
maxSubSegment(sum,N);
39
if
(result<
re)
40
result=
re;
41
}
42
}
43
cout<<
result;
44
return
0
;
45
}
【版权声明】转载请注明出处 http://www.cnblogs.com/TenosDoIt/archive/2013/04/16/3025007.html
