/ OIer TK / 题库 /

月饼盒

月饼盒

测试数据来自 system/1255

背景

中秋节了,CCC老师决定去送礼。

描述

一个被分为 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

输出格式

输出最大月饼数。

样例1

样例输入1

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

样例输出1

17

提示

10 3 4
这个矩形的糖果数最大

来源

From OIBH.
dfh改编!

信息

ID
1245
难度
9
分类
动态规划 | 其他 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者