题目名称 532. [USACO11MAR] Brownie Slicing G
输入输出 brownie.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarzqzas 于2011-03-17加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:13, 提交:15, 通过率:86.67%
Gravatarchangxv 100 0.043 s 2.24 MiB C++
Gravatarchangxv 100 0.049 s 2.24 MiB C++
Gravatar瑆の時間~無盡輪迴·林蔭 100 0.137 s 14.65 MiB C++
Gravatarsyzhaoss 100 0.194 s 4.62 MiB C++
GravatarHXF 100 0.251 s 2.23 MiB C++
Gravatarkaaala 100 0.268 s 1.26 MiB C++
Gravatar小福鑫 100 0.297 s 4.79 MiB C++
Gravatar小福鑫 100 0.318 s 4.78 MiB C++
Gravatar小福鑫 100 0.322 s 4.78 MiB C++
GravatarDHP1078 100 0.326 s 1.01 MiB C++
本题关联比赛
2011.3.17
2011.3.17
关于 Brownie Slicing G 的近10条评论(全部评论)

532. [USACO11MAR] Brownie Slicing G

★★☆   输入文件:brownie.in   输出文件:brownie.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

Bessie 烤了一个长方形的布朗尼,可以看作是一个 $R \times C$ 的网格($1 \le R \le 500$;$1 \le C \le 500$),由小方块组成。在第 $i$ 行,第 $j$ 列的方块中有 $N_{ij}$($0 \le N_{ij} \le 4,000$)颗巧克力豆。

Bessie 想把布朗尼分成 $A \times B$ 块($1 \le A \le R$;$1 \le B \le C$):每头牛一块。布朗尼的切割方式是先进行 $A-1$ 次水平切割(总是在整数坐标上),将布朗尼分成 $A$ 条带。然后每条带独立地进行 $B-1$ 次垂直切割,也是在整数边界上。其他 $A \times B - 1$ 头牛各自选择一块布朗尼,剩下最后一块给 Bessie。由于它们很贪心,它们会把巧克力豆最少的一块留给 Bessie。

假设 Bessie 以最优方式切割布朗尼,求 Bessie 能获得的最多巧克力豆数。

例如,考虑一个 5 行 4 列的布朗尼,巧克力豆分布如下:

1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Bessie 必须将布朗尼分成 4 条水平带,每条带有两块。Bessie 可以这样切割布朗尼:

1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1
因此,当其他贪心的牛选择它们的布朗尼块时,Bessie 仍然可以得到 3 颗巧克力豆。

【输入格式】

第 1 行:四个用空格分隔的整数:$R$,$C$,$A$ 和 $B$

第 2 行到第 $R+1$ 行:第 $i+1$ 行包含 $C$ 个用空格分隔的整数:$N_{i1}, ..., N_{iC}$

【输出格式】

第 1 行:一个整数:Bessie 在她的布朗尼上能保证获得的最多巧克力豆数

【样例输入】

5 4 4 2 
1 2 2 1 
3 1 1 1 
2 0 1 3 
1 1 1 1 
1 1 1 1 

【样例输出】

3