文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 求最大子矩阵的两种思路
侵权投诉

求最大子矩阵的两种思路

12

求最大子矩阵的两种思路

长沙市雅礼中学 贺一骏

编者:求最大子矩阵问题是很常见的一类问题,具有很强的代表性,通过这个问题,可以派生出更加复杂的问题,也可以学到很多常用的问题处理手段。

问题描述

一个被分为 n*m个格子的月饼盒,第 i 行第 j 列位置的格子里面有 a [ i , j ]个月饼。本来CCC老师打算送这盒月饼给某人的,但是就在要送出月饼盒的前一天晚上,一只极其可恶的老鼠夜袭月饼盒,有部分格子被洗劫并且穿了洞。CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒,新的月饼盒不能有洞,并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。

任务:请帮CCC老师设计一个程序,计算一下新月饼盒最多能够保留多少月饼。 输入

文件的第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a [ i , j ],如果这个数为 0 ,则表示这个位置的格子被洗劫过。其中:1 ≤ n,m ≤ 300,0 ≤a [ i , j ]≤ 255

输出

在文件中写入最大月饼数。 样例

Sample Input 3 4 1 2 3 4 5 0 6 3 10 3 4 0

Sample Output 17 分析

该问题实际上是求在给定平面区域中找出一个最大的子矩形,要求该矩形不能包含某些限定的格子。

方法一:

我们初次见到这个问题,可能最直接的想法就是枚举。即枚举每个矩阵的左上角坐标(x1,y1)和右下角坐标(x2,y2),然后统计这个矩阵是否满足题设条件。

第1页

你可能喜欢

热门文档

相关文档

  • 最大子矩阵问题

    求最大子矩阵的两种思路 5页 免费 矩阵的最大子矩阵和 暂无评价 2页 免费...最大子矩阵问题 新一篇: MAC 地址完美攻略 最大子矩阵问题: 问题描述:(具体...

  • 最大子矩阵的枚举方法

    求最大子矩阵的两种思路 5页 免费 最大子序列和最大子矩阵 3页 免费 最大子矩阵 5页 免费 晋城职业技术学院开题报告... 暂无评价 4页 免费 §1 同角...

  • 最大子矩阵的枚举方法

    最大子矩阵的枚举方法_计算机软件及应用_IT/计算机...了一个障碍点的极大子矩形,此外, 还有两类遗漏的...在一个矩形中存在S个障碍点,要 求找出最大的不...

  • 【论文】求循环矩阵的两种简便方法

    求循环矩阵的两种简便方法_专业资料。探讨循环矩阵的求逆问题,提出求解循环矩阵... 维普网 中国最大最早的专业内容网站 0 0 0.0 文档数 浏览总量 总评分...

  • 最大字段问题-含最大子矩阵和m子段和

    [n/2+1:n],分别求出这2段的最大子段和, 则a[1:n]的最大子段和有3...转化方法: 我们把这个矩阵划分成n个“条”,条的长度为1到 m,通过两个for...

  • 矩阵的最大子矩阵和

    矩阵的最大子矩阵和_数学_自然科学_专业资料。#include<iostream> #include<... 求最大子矩阵的两种思路 5页 免费 从连续最大和到最优子矩... 14页 ...

  • 动态规划 最长子串与最大子矩阵问题

    我们想借助求最长子串的方法来求最大矩阵, 假设矩 阵为 m*n,我们将每一行...实现最大字串问题描述大概就是给定 2 个字符串,找出他们两个共有的最长字符串...

  • 最大子矩阵

    DP问题——最大子矩阵: [**比赛日期变化**]鉴于11月10日有期中考试,11月份... DP:最大连续子段和 到最... 9页 1下载券 求最大子矩阵的两种思路 5页...

  • 最大子序列和最大子矩阵

    :给定一个数组,其中元素有正,也有负,找去其中一个连续子序列 ,使 和最大。... 求最大子矩阵的两种思路 5页 免费 DP:最大连续子段和 到最... 9页 1...

  • 矩阵环的极大的广义Armendariz子环

    求最大子矩阵的两种思路 5页 免费 最大子矩阵的枚举方法 42页 免费... 矩阵环 的极大的广义 Aedr 子环 maazni 7 5 n1 01 我 们 有=n∈I 们...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email