| 题目名称 | 552. [Matrix模拟赛] 吃西瓜 |
|---|---|
| 输入输出 | matrix.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2011-07-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：31， 提交：46， 通过率：67.39% | ||||
 Makazeu |
100 | 0.359 s | 0.66 MiB | C++ |
 cstdio |
100 | 0.375 s | 0.97 MiB | C++ |
 努力吧 |
100 | 0.536 s | 1.00 MiB | C++ |
 outman |
100 | 0.537 s | 1.00 MiB | C++ |
 胡嘉兴 |
100 | 0.591 s | 0.79 MiB | C++ |
 临轩听雨ゐ |
100 | 0.661 s | 27.13 MiB | C++ |
 KZNS |
100 | 0.719 s | 0.41 MiB | C++ |
 hjr1995 |
100 | 0.827 s | 0.82 MiB | Pascal |
 苏轼 |
100 | 0.893 s | 0.86 MiB | C++ |
|
KZNS |
100 | 1.038 s | 0.46 MiB | C++ |
| 本题关联比赛 | |||
| 数据结构练习 | |||
| 关于 吃西瓜 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
补充：启示：嵌套循环中，“小循环”尽量在外层
| ||||
|
四维枚举i1,j1,i2,j2，高先不枚举，实际意义是先从上到下贯穿地切下来一竖条西瓜。翔！
剩下的用一位的思想做（DP）。 为了方便可以开一个s[i][j][k]，表示第i层从(1,1)到(j,k)的营养值的和。 | ||||
|
Makazeu
2012-11-02 00:42
1楼
| ||||
Truth.Cirno
feng
[说明]此题中出现的所有数全为整数
[背景]SubRaY有一天得到一块西瓜,是长方体形的....
[题目描述]SubRaY发现这块西瓜长m厘米,宽n厘米,高h厘米.他发现如果把这块西瓜平均地分成m*n*h块1立方厘米的小正方体,那么每一小块都会有一个营养值(可能为负,因为西瓜是有可能坏掉的,但是绝对值不超过200).
现在SubRaY决定从这m*n*h立方厘米的西瓜中切出mm*nn*hh立方厘米的一块小西瓜(一定是立方体形,长宽高均为整数),然后吃掉它.他想知道他最多能获得多少营养值.(0<=mm<=m,0<=nn<=n,0<=hh<=h.mm,nn,hh的值由您来决定).
换句话说,我们希望从一个m*n*h的三维矩阵中,找出一个三维子矩阵,这个子矩阵的权和最大.
一个2*3*4的例子,最优方案为切红色2*3*1部分
[输入][matrix.in]
首行三个数h,m,n(注意顺序),分别表示西瓜的高,长,宽.
以下h部分,每部分是一个m*n的矩阵,第i部分第j行的第k个数表示西瓜第i层,第j行第k列的那块1立方厘米的小正方体的营养值.
[输出][matrix.out]
SubRaY所能得到的最大营养值
[样例输入]
2 3 4
4 1 2 8
0 5 -48 4
3 0 1 9
2 1 4 9
1 0 1 7
3 1 2 8
[样例输出]
45
[数据范围]
对于30%的数据,h=1,1<=m,n<=10
对于全部的数据,1<=h<=32,1<=m,n<=50,保证h<=m,n