P3017 [USACO11MAR]布朗尼切片Brownie Slicing

    • 120通过
    • 265提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 二分答案 枚举,暴力 USACO 2011 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Bessie has baked a rectangular brownie that can be thought of as an RxC grid (1 <= R <= 500; 1 <= C <= 500) of little brownie squares. The square at row i, column j contains N_ij (0 <= N_ij <= 4,000) chocolate chips.

    Bessie wants to partition the brownie up into A*B chunks (1 <= A <= R; 1 <= B <= C): one for each of the A*B cows. The brownie is cut by first making A-1 horizontal cuts (always along integer

    coordinates) to divide the brownie into A strips. Then cut each strip *independently* with B-1 vertical cuts, also on integer

    boundaries. The other A*B-1 cows then each choose a brownie piece, leaving the last chunk for Bessie. Being greedy, they leave Bessie the brownie that has the least number of chocolate chips on it.

    Determine the maximum number of chocolate chips Bessie can receive, assuming she cuts the brownies optimally.

    As an example, consider a 5 row x 4 column brownie with chips

    distributed like this:

    1 2 2 1

    3 1 1 1

    2 0 1 3

    1 1 1 1

    1 1 1 1

    Bessie must partition the brownie into 4 horizontal strips, each with two pieces. Bessie can cut the brownie like this:

    1 2 | 2 1


    3 | 1 1 1


    2 0 1 | 3


    1 1 | 1 1

    1 1 | 1 1

    Thus, when the other greedy cows take their brownie piece, Bessie still gets 3 chocolate chips.

    Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由R*C(1 <= R,C <= 500)个小的巧克力蛋糕组成的。第i行,第j列的蛋糕有N_ij(1<= N_ij <= 4,000)块巧克力碎屑。

    Bessie想把蛋糕分成A*B块,(1 <= A<= R,1 <= B <= C): 给A*B只奶牛。蛋糕先水平地切A-1刀(只能切沿整数坐标切)来把蛋糕划分成A块。然后再把剩下来的每一块独立地切B-1刀,也只能切沿整数坐标切。其他A*B-1只奶牛就每人选一块,留下一块给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条,每条分成2块。Bessie能像这样切蛋糕:

    输入输出格式

    输入格式:

    * Line 1: Four space-separated integers: R, C, A, and B

    * Lines 2..R+1: Line i+1 contains C space-separated integers: N_i1, ..., N_iC

    输出格式:

    * Line 1: A single integer: the maximum number of chocolate chips that Bessie guarantee on her brownie

    输入输出样例

    输入样例#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 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。