P3017 [USACO11MAR] Brownie Slicing G
[P3017 USACO11MAR] Brownie Slicing G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题面翻译
Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由 \(R\times C(1\leq R,C\leq 500)\) 个小的巧克力蛋糕组成的。第 \(i\) 行，第 \(j\) 列的蛋糕有 \(N_{i,j}(N_{i,j}\leq 4000)\) 块巧克力碎屑。
Bessie想把蛋糕分成 \(A\times B(1\leq A\leq R,1\leq B\leq C)\) 块，:给 \(A\times B\) 只奶牛。蛋糕先水平地切 \(A-1\) 刀（只能切沿整数坐标切）来把蛋糕划分成 \(A\) 块。然后再把剩下来的每一块独立地切 \(B-1\) 刀，也只能切沿整数坐标切。其他 \(A\times B-1\) 只奶牛就每人选一块，留下一块给Bessie。由于贪心，他们只会留给Bessie巧克力碎屑最少的那块。求出Bessie最优情况下会获得多少巧克力碎屑。
例如，考虑一个\(5\times4\)的蛋糕，上面的碎屑分布如下图所示：
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1
Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕:
1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1
这样，Bessie至少能获得 \(3\) 块巧克力碎屑
题目描述
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
样例输入 #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
思路
先二分答案。
对于每一行，满足条件就切一刀，不满足就继续累加
如果这一行满足 \(b\) 刀就换横着切一刀，并跳到下一行。
如果不满足 \(b\) 刀就加上下一行一起切
最后判断一下图上是否有 \(a\) 刀就好了
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 505;
int mp[N][N] , n , m , a , b;
bool ck (int num) {
int x = 1 , y = 1 , a1 = 0 , k , sum , b1;
while (y <= n) {
k = 1 , sum = b1 = 0;
while (k <= m) {
fu (i , x , y)
sum += mp[i][k];
if (sum >= num)
sum = 0 , b1 ++;
k ++;
}
if (b1 >= b)
x = y + 1 , a1 ++;
y ++;
}
return a1 >= a;
}
int main () {
int l = 0 , r = 0;
scanf ("%d%d%d%d" , &n , &m , &a , &b);
fu (i , 1 , n) {
fu (j , 1 , m) {
scanf ("%d" , &mp[i][j]);
r += mp[i][j];
}
}
int mid , ans = 0;
while (l <= r) {
mid = l + r >> 1;
if (ck (mid)) ans = mid , l = mid + 1;
else r = mid - 1;
}
printf ("%d" , ans);
return 0;
}