[USACO11MAR] 巧克力蛋糕切分 G

题目描述

贝茜烤了一块长方形的巧克力蛋糕，蛋糕可以看作一个由 R 行 C 列小蛋糕方块组成的网格（1 ≤ R ≤ 500；1 ≤ C ≤ 500）。第 i 行第 j 列的蛋糕方块上含有 N_ij 颗巧克力豆（0 ≤ N_ij ≤ 250）。

贝茜想要把蛋糕切分成 A×B 块（1 ≤ A ≤ R；1 ≤ B ≤ C），分给 A×B 头奶牛。 切分规则如下：

1. 首先进行 A−1 次水平切割（沿整数坐标切割），将蛋糕分成 A 个横条；
2. 然后独立地对每个横条进行 B−1 次垂直切割（同样沿整数边界切割）。

其他贪婪的奶牛会优先挑选巧克力豆最多的蛋糕块，留给贝茜的一定是所有块中巧克力豆数量最少的那一块。

请你计算：在最优切割方案下，贝茜能保证得到的最大巧克力豆数量是多少。

样例说明： 一个 5 行 4 列的蛋糕，巧克力豆分布如下：

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

贝茜必须切分成 4 个横条，每个横条再切 2 块。 最优切割方式如下：

1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1

最终，贝茜能得到 3 颗巧克力豆。

输入格式

• 第 1 行：四个用空格分隔的整数 R, C, A, B
• 第 2 至 R+1 行：第 i+1 行包含 C 个用空格分隔的整数 N_i1, N_i2, ..., N_iC

输出格式

• 第 1 行：一个整数，表示贝茜能保证获得的最大巧克力豆数量

输入样例 1：

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

输出样例 1：

3 

提示

（暂无提示）

标签：P3017|2011|二分|USACO|枚举|前缀和

来源

P3017|[USACO11MAR] Brownie Slicing G