BZOJ 2196: [Usaco2011 Mar]Brownie Slicing( 二分答案 )

BZOJ 2196: [Usaco2011 Mar]Brownie Slicing( 二分答案 )

二分答案就可以了....

-----------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cctype>
 
using namespace std;
 
typedef long long ll;
 
inline int read() {
char c = getchar();
int ret = 0;
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0';
return ret;
}
 
const int maxn = 509;
 
int mat[maxn][maxn], sum[maxn][maxn], t[maxn], N, M, A, B;
 
bool ok(int p, int c, int x) {
if(sum[c][M] - sum[p][M] < x * B) return false;
for(int i = 0; i <= M; i++)
t[i] = sum[c][i] - sum[p][i];
int _c = 1, _p = 0;
for(int i = 0; i < B; i++) {
while(t[_c] - t[_p] < x) 
if(++_c > M) return false;
_p = _c;
}
return true;
}
 
bool check(int x) {
int p = 0, c = 1;
for(int i = 0; i < A; i++) {
while(!ok(p, c, x)) 
if(++c > N) return false;
p = c;
}
return true;
}
 
int main() {
N = read(); M = read(); A = read(); B = read();
for(int i = 1; i <= N; i++) {
sum[i][0] = 0;
for(int j = 1; j <= M; j++)
sum[i][j] = sum[i][j - 1] + (mat[i][j] = read());
}
for(int j = 1; j <= M; j++) {
sum[0][j] = 0;
for(int i = 1; i <= N; i++)
sum[i][j] += sum[i - 1][j];
}
int ans, L = 0, R = int(1e9);
while(L <= R) {
int m = (L + R) >> 1;
if(check(m))
ans = m, L = m + 1;
else
R = m - 1;
}
cout << ans << "\n";
return 0;
}

-----------------------------------------------------------------------

2196: [Usaco2011 Mar]Brownie Slicing

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 183  Solved: 123
[Submit][Status][Discuss]

Description

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能像这样切蛋糕: 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 因此,其他贪得无厌的牛拿完后,Bessie仍能够拿走3个巧克力碎屑。

Input

* 第1行: 四个空格隔开的数: R, C, A ,B * 第2-R+1行: 第i+1行有C个整数, N_i1 , N_i2 .. N_iC

Output

* 第1行: 一个整数: Bessie保证能拿到的最多碎屑数

Sample Input

5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Sample Output

3

HINT

Source

上一篇:bzoj 1816: [Cqoi2010]扑克牌


下一篇:java实现ftp文件的上传与下载