題目地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1074
這道題的dP是基于 “最大子段和” 的dp方法
例如求數(shù)組 ?1 ?2 ?-3 ?4；-5 ?6 ?-1 ?8 的最大子矩陣和，可以把兩行相加得到數(shù)組-4 ?8 ?-4 ?12，對(duì)這個(gè)數(shù)組求最大子段和為8+-4+12=16，所以矩陣對(duì)應(yīng)的最大子矩陣為2 ?-3 ?4；?6 ?-1 ?8
那么可以利用以上思想，對(duì)于m*n的矩陣A，選取他的第 i 行到第 j 行的數(shù)據(jù)組成子矩陣Aij (j-i+1行n列)，Aij 對(duì)應(yīng)的最大子段和可以如下求得：對(duì)每一列的值進(jìn)行累加得到一個(gè)一維數(shù)組(1*n)，對(duì)該數(shù)組求最大字段和（ 其中 ?1=< i=<j<=m ）。
綜上所述，A的最大子矩陣和為：max（ subMatrix(Aij) ） ，其中1=< i=<j<=m ，subSegment(Aij) 表示Aij?對(duì)應(yīng)的最大子段和。
?
上代碼：
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
}
?【版權(quán)聲明】轉(zhuǎn)載請(qǐng)注明出處? http://www.cnblogs.com/TenosDoIt/archive/2013/04/16/3025007.html
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
