文档章节

最大子矩阵 轉載

電泡泡
 電泡泡
发布于 2013/07/30 00:08
字数 831
阅读 22
收藏 0

最大子矩阵  

2009-08-30 20:37:05|  分类: ACM - DP|字号 订阅

最大子矩阵也是经典DP,这样的基础题在POJ上的第1050题,

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1050

题目大意:读入一个n*n的数组,,从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大。

比如:

 0  -2   -7   0
 9   2   -6   2
-4   1   -4   1
-1   8    0  -2

截取出来的矩阵,和为15:

 9   2 
-4   1 
-1   8 

       最大子矩阵和,即在一个n*m的矩阵中找出其子矩阵其和最大,如果直接枚举每一个子矩阵是不现实的,为了简化计算的过程,可以对矩阵进行转换。

       一个子矩阵是由原矩阵中的行列组成,在求解的过程中只要找出其最大的和,在查找一维矩阵(即一维数组)时,求n个元素的和最大的子区间,我们采用的思想是扫描这一维矩阵,用max表示出现的和的最大值,sum表示从左至右的求和的值,我们要考虑sum值出现的情况,如果sum < 0这种求和是没有意义的,因为任何数加上一个小于0的负数其值必然减少,也就是这时是不可能出现最大的值,这样就可以采用将要加上的元素值赋给sum,以该点做为下一个求和的开始,还有一点就是在使用sum计算求和时,我们只有在扫描所有元素才知道出现子区间和的最大值是什么,也就是只要为sum>0情况则再加上一元素,该元素的值必然会增大,也就是有可能出现sum的值变大出现sum > max的情况,虽然也会出现sum减少的情况,但是我们始终有max记录在求和过程中出现过的最大值,如果max < sum,就更新max的值,最终的max便是我们要求的一维矩阵的最大值。

       有了一维数组的基础,对于二维数组,我们可以将它化为多列单列的数字来做,相当于我们将一个长方形压扁,使宽度为1。引入辅助数组dp, dp[j][i]代表第 j 列从第 1 行开始的数字累加到第 i 行的值,每次压扁是可以用 dp[j][i2] - dp[j][i1 - 1] 来表示第 j 列从第 i1 行开始倒第 i2 行的数字之和。然后用一维数组的最大字段和的方法来做,这种方法的时间复杂度是O(n^3)。

AC Code:

#include <iostream>

using namespace std;

const int N = 110;

int dp[N][N], a[N][N];

int n;

 

int main()

{

       int i, j, i1, i2;

       int max, sum, tmp;

       while (scanf ("%d", &n) != EOF )

       {

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

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

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

              memset (dp, 0, sizeof (dp));

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

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

                            dp[j][i] = dp[j][i - 1] + a[i][j];

              max = 0;

              for (i1 = 1; i1 <= n; i1++)

                     for (i2 = i1; i2 <= n; i2++)

                     {

                            tmp = dp[1][i2] - dp[1][i1 - 1];

                            sum = tmp;

                            for (j = 2; j <= n; j++)

                            {

                                   if (sum > 0)

                                          sum += dp[j][i2] - dp[j][i1 - 1];

                                   else sum = dp[j][i2] - dp[j][i1 - 1];

                                   if (tmp < sum) tmp = sum;

                            }

                            if (tmp > max) max = tmp;

                     }

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

       }

       return 0;

}

© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 23
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
在 YouTube 網址後面加上 my 就能快速下載、備份影片 Mp4 格式

(Copyright: emevil / 123RF Stock Photo) 很多人會選擇將影片上傳到 YouTube 或 Facebook 分享,即使是使用於個人網站、部落格,也會利用內嵌方式節省流量,不過上傳到網路後必須考量到日...

w116858389
2018/04/06
0
0
透過proxychains讓不支持代理的程序通過代理上網

一直知道tsocks有這樣的功能,但今天用時確連不上SSH轉發的socks5代理服務器。於是google了一下,發現有同樣功能的proxychains 。簡述如下: 安裝: yum install proxychains 配置:配置文件...

litescript
2012/04/02
0
0
oschina有文件中轉站嗎?

我想把在公司做的項目上傳到一個文件中轉站,然後回家把項目下載到自己的電腦中。現在各郵箱已經被公司屏蔽了,所以郵箱不行了。咋辦呢?

喜之郎
2011/12/18
245
7
在 Windows 下安裝 ImageMagick 并制作缩略图

此方式是經由站長建議來實作的喔.. 那天與站長閒聊GD與系統縮圖程式的優缺點. 經小弟省思許多還是贊同站長的建議... 利用imagemagick與PHP來作搭配.. 果然...方便渡給100分喔.. 小弟提供一個...

红薯
2009/01/25
2.3K
4
ubuntu下使用ipod shuffle

安装gtkpod就可以了,然后就图形界面。 在不能使用 iTunes 的 Ubuntu 底下,如何使用 iPod 總是需要經過一點研究,本篇就來紀錄一下在 Ubuntu 底下與 iPod shuffle 2 傳輸的方法吧! 本篇的主...

枫言风语
2012/12/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

微信网页授权获取用户信息(ThinkPHP5)+ 微信发送客服消息(一)

以thinkphp5为实例,创建控制器 class Kf extends Controller { /** * [protected description]微信公众号appid * @var [type] */ protected $appid = "xxxxxxxxxxxxxxx"; /** * [protected......

半缘修道半缘君丶
20分钟前
0
0
《拆掉思维里的墙》的读后感作文900字

《拆掉思维里的墙》的读后感作文900字: 与以往不同,《拆掉思维里的墙》首先吸引我的是那一幅幅有趣的插画,寥寥几笔配上一句话,细细品味很有意思,很有哲理。 《拆掉思维里的墙》是2010年...

原创小博客
22分钟前
1
0
weblogic 启动项目失败,JMS 队列通过http 方式访问

java.rmi.ConnectException: Destination unreachable; nested exception is: java.net.ConnectException: Tried all: '1' addresses, but could not connect over HTTP to server: '127.0......

fengzhi714
22分钟前
1
0
SourceTree 推拉 GitHub 代码时弹出“Password Required”

在 MacBook 上使用 https 访问 GitHub 库时,SourceTree 老是会弹出密码提示框“Password Required”,即使选中保存到钥匙链也没用,麻烦。 但是用 idea、vscode 之类的却正常,检查钥匙链发...

郁也风
31分钟前
1
0
powerdesigner连接Mysql数据库

此次使用Mysql8.0和powerdesigner16.5 1、新建一个pdm 这里有个疑问,本人的mysql的版本是8.0,但如下图DBMS里最高只有mysql5.0,但以后没什么影响,所以未深究。 2、点击菜单栏里database,...

jxlgzwh
53分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部