4937：[USACO11MAR] Brownie Slicing G

# [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