《P3017 [USACO11MAR] Brownie Slicing G》

题目描述

Bessie 烤了一个长方形的布朗尼，可以看作是一个 R×C 的网格（1≤R≤500；1≤C≤500），由小方块组成。在第 i 行，第 j 列的方块中有 Nij​（0≤Nij​≤4,000）颗巧克力豆。

Bessie 想把布朗尼分成 A×B 块（1≤A≤R；1≤B≤C）：每头牛一块。布朗尼的切割方式是先进行 A−1 次水平切割（总是在整数坐标上），将布朗尼分成 A 条带。然后每条带独立地进行 B−1 次垂直切割，也是在整数边界上。其他 A×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 个用空格分隔的整数：Ni1​,...,NiC​

输出格式

* 第 1 行：一个整数：Bessie 在她的布朗尼上能保证获得的最多巧克力豆数

显示翻译

题意翻译

输入输出样例

输入 #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 

说明/提示

（由 ChatGPT 4o 翻译）

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,l,r,ans,s[505][505];
bool check(int x){
    int tmp=0,now=0;
    //tmp表示切了几条
    for(int i=1;i<=n;++i){
    //枚举条
        int k=0;
        //k表示切了几块
        for(int j=1,lst=0;j<=m;++j)
        //枚举块
            if(s[i][j]-s[i][lst]-s[now][j]+s[now][lst]>=x){
            //是否能切成一块
                k++;
                lst=j;
            }
        if(k>=b){
        //是否能切成一条
            tmp++;
            now=i;
        }
    }
    return tmp>=a;
}
int main(){
    cin>>n>>m>>a>>b;
    for(int i=1;i<=n;++i)
        for(int j=1,x;j<=m;++j){
            cin>>x;
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
            //计算前缀和
        }
    r=s[n][m]/(a*b);
    //二分答案
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}