[Usaco2011 Mar]Brownie Slicing
时间限制：10s 空间限制：259MB
题目描述
Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由R*C(1 <= 0="" 1="" 2="" 3="" r,c="" <="500)个小的巧克力蛋糕组成的。" 第i行，第j列的蛋糕有n_ij(1="" bessie想把蛋糕分成a*b块，(1="" 给a*b只奶牛。蛋糕先水平地切a-1刀="" （只能切沿整数坐标切）来把蛋糕划分成a块。然后再把剩下来的每一块独立地切b-1刀，="" 也只能切沿整数坐标切。其他a*b-1只奶牛就每人选一块，留下一块给bessie。由于贪心，="" 他们只会留给bessie巧克力碎屑最少的那块。="" 求出bessie最优情况下会获得多少巧克力碎屑。="" 例如，考虑一个5*4的蛋糕，上面的碎屑分布如下图所示：="" bessie必须把蛋糕切成4条，每条分成2块。bessie能像这样切蛋糕:="" |="" ---------="" 因此，其他贪得无厌的牛拿完后，bessie仍能够拿走3个巧克力碎屑。="" p="">
输入格式
* 第1行: 四个空格隔开的数: R, C, A ，B * 第2-R+1行: 第i+1行有C个整数, N_i1 , N_i2 .. 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
提示
没有写明提示
题目来源
Gold