随笔:78 文章:7 评论:38 引用:0
从零开始
记录成长
C++博客
首页
发新随笔
发新文章
联系
聚合
管理
继续动规
pku 1050 最大子矩阵和
题目大意:
给定一个N*N的矩阵,求其中一个子矩阵所有元素的和最大,输出最大值。
题解:
这道题很早就见过了,一直不会做,学了最大连续和,但是没能成功迁移,看别人的解题报告也是很久才理解。
主要思想就是把二维的矩阵转化成一位的数字串,然后求最大子串和。转换的时候,为了保证最大子串构成的是完整的矩形,所以串里的每一个元素都得是一列的和。枚举子矩阵的起始行和高度,如从第i行开始,到第j行结束,每一对 i 和 j,对每一列(1~n)求和,然后求1~n串的最大子串和。
#include
<
stdio.h
>
#include
<
string
.h
>
const
int
N
=
110
;
int
g[N][N], f[N];
int
main()
{
int
n;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
{
memset(f,
0
,
sizeof
(f));
for
(
int
i
=
1
; i
<=
n; i
++
)
for
(
int
j
=
1
; j
<=
n; j
++
)
scanf(
"
%d
"
,
&
g[i][j]);
int
mx
=-
100000000
;
for
(
int
i
=
1
; i
<=
n; i
++
)
for
(
int
j
=
i ; j
<=
n; j
++
)
{
memset(f,
0
,
sizeof
(f));
for
(
int
s
=
1
; s
<=
n; s
++
)
for
(
int
k
=
i; k
<=
j; k
++
)
f[s]
+=
g[k][s];
int
tmp
=
0
;
for
(
int
s
=
1
; s
<=
n; s
++
)
{
if
(tmp
>
0
)
tmp
+=
f[s];
else
tmp
=
f[s];
mx
=
mx
>
tmp
?
mx:tmp;
}
}
printf(
"
%d\n
"
,mx);
}
return
0
;
}
发表于 2010-09-03 22:58
未央
阅读(210)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
CALENDER
<
2011年7月
>
日
一
二
三
四
五
六
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(6)
给我留言
查看公开留言
查看私人留言
随笔档案
2020年11月 (1)
2020年1月 (1)
2018年11月 (1)
2018年9月 (2)
2017年10月 (1)
2017年9月 (1)
2017年7月 (1)
2015年1月 (1)
2014年11月 (2)
2014年3月 (1)
2014年2月 (1)
2014年1月 (1)
2013年6月 (1)
2013年5月 (2)
2013年4月 (1)
2013年3月 (3)
2012年11月 (1)
2012年7月 (1)
2012年6月 (1)
2012年2月 (2)
2011年12月 (1)
2011年11月 (2)
2011年8月 (1)
2011年7月 (2)
2011年6月 (3)
2011年4月 (1)
2011年3月 (6)
2011年2月 (3)
2011年1月 (2)
2010年12月 (2)
2010年11月 (4)
2010年9月 (3)
2010年5月 (1)
2010年2月 (2)
2009年10月 (2)
2009年9月 (5)
2009年8月 (6)
2009年7月 (3)
2008年7月 (3)
文章档案
2012年2月 (1)
2008年7月 (6)
搜索
最新评论
1. re: Palindrome Partitioning II - leetcode
我想问一下为什么不能用dfs+一个记忆化数组判断回文串来做呢?
--冯思峰
2. re: Visual Studio 2008 OpenGL配置
感谢~
--无叶莲
3. re: 点集的最小圆覆盖 zju 1450
我这运行是正确的,如有错误,请大家指出
--zzc
4. re: 点集的最小圆覆盖 zju 1450
@JimZ ,LZ的代码没错啊,若有错误请说明,在什么情况下会错,要不就不要乱说啊,那样不负责任吧。
--aaa
5. re: 0xC0000005: 写入位置 0xcccccccc 时发生访问冲突
我刚解决掉,我是用的模板存储的图片,其中有一部分呢我不想改变,我就又复制了一份,在调试时,这两个就冲突了,我将那个复制的删除掉就好了。
--wobuaishangdiao
阅读排行榜
1. Qt 打开文件的默认路径 QFileDialog::getOpenFileName()(25702)
2. Qt中将QString转换为char *或者相反(13778)
3. topcoder 赚钱(9180)
4. OpenGL里关于鼠标响应的函数(9106)
5. Visual Studio 2008 OpenGL配置(7490)
评论排行榜
1. 有根树的同构 和 无根树的同构(8)
2. 点集的最小圆覆盖 zju 1450(5)
3. 爱与恨的记忆(3)
4. pku 3338 Rectangle Cutting 侥幸过的,还是有些难度的(2)
5. c++ 读取目录下的文件名(2)
Powered By:
博客园
模板提供
:
沪江博客