| 题目名称 | 532. [USACO11MAR] Brownie Slicing G |
|---|---|
| 输入输出 | brownie.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过:13, 提交:15, 通过率:86.67% | ||||
|
|
100 | 0.043 s | 2.24 MiB | C++ |
|
|
100 | 0.049 s | 2.24 MiB | C++ |
|
|
100 | 0.137 s | 14.65 MiB | C++ |
|
|
100 | 0.194 s | 4.62 MiB | C++ |
|
|
100 | 0.251 s | 2.23 MiB | C++ |
|
|
100 | 0.268 s | 1.26 MiB | C++ |
|
|
100 | 0.297 s | 4.79 MiB | C++ |
|
|
100 | 0.318 s | 4.78 MiB | C++ |
|
|
100 | 0.322 s | 4.78 MiB | C++ |
|
|
100 | 0.326 s | 1.01 MiB | C++ |
| 本题关联比赛 | |||
| 2011.3.17 | |||
| 2011.3.17 | |||
| 关于 Brownie Slicing G 的近10条评论(全部评论) |
|---|
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