[动态规划]pku1050

枚举矩形的上边和下边，花费O(n²)，把问题转化成一维的最大M子段和，做一个O(n)的DP。

#include <stdio.h>

const int maxint = 2147483647;

int max(int n, int *a)

{

int sum = -maxint, b = 0;

for (int i = 1; i <= n; i++)

{

if (b > 0)

b += a[i];

else

b = a[i];

sum >?= b;

}

return sum;

}

int a[101][101];

int maxsum(int n)

{

int sum = -maxint, *b = new int[n + 1];

for (int i = 1; i <= n; i++)

{

for (int j = 1; j <= n; j++)

b[j] = a[i][j];

for (int j = i + 1; j <= n; j++)

{

for (int k = 1; k <= n; k++)

b[k] += a[j][k];

sum >?= max(n, b);

}

return sum;

}

int main()

{

int n;

scanf("%d", &n);

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

scanf("%d", &a[i][j]);

printf("%d\n", maxsum(n));

return 0;

}

posted on 2007-08-26 13:51 Felicia 阅读(1002) 评论(6) 编辑收藏引用所属分类: 动态规划

Comments

# re: [动态规划]pku1050
@潘帕斯雄鹰
Posted @ 2007-08-30 23:16
大牛天天更新，小菜一定天天过来踩回复更多评论
# re: [动态规划]pku1050
Gchris
Posted @ 2007-12-07 16:28
大牛同学,你好!
为什么你的blog里有 sum >?= max(n, b); 这样的语句,是不是blog系统出错了? 回复更多评论
# re: [动态规划]pku1050
Felicia
Posted @ 2007-12-07 20:07
我不是大牛。
blog系统没错，>?=是运算符回复更多评论
# re: [动态规划]pku1050
Gchris
Posted @ 2007-12-08 23:25
@Felicia
可是我把它拷到 VC 里不能运行
回复更多评论
# re: [动态规划]pku1050
Gchris
Posted @ 2007-12-08 23:28
>?=
是什么意思？回复更多评论
# re: [动态规划]pku1050
Felicia
Posted @ 2007-12-10 21:23
……不要用VC编译，用G++编译回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: [动态规划]O(n^2 / logn)的LCS [动态规划] pku1458 最长公共子序列 [动态规划]pku1080 [动态规划]pku1338 [动态规划]pku3420 [动态规划]pku1191 [动态规划]pku1179 [动态规划]pku1189 [动态规划]pku1185 [动态规划]pku1163

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

导航

常用链接

留言簿(21)

随笔分类(145)

随笔档案(149)

相册

ACMers

Pretty Girls

最新随笔

搜索

最新评论

阅读排行榜

评论排行榜