蛋糕

$蛋糕$蛋糕

题目链接：jzoj 3918

题目大意

有一个$R*C$R∗C的蛋糕，每一个蛋糕格都有一个值。横切三道，竖切三道，怎样切才能使蛋糕值和最小的一块蛋糕的蛋糕值最大。

样例输入

5 5
95998
21945
23451
99798
74083

样例输出

3

样例解释

数据范围

$40\%$40%的数据， $4 <= R$4<=R , $C <= 10$C<=10。
$60\%$60%的数据， $4 <= R , C <= 20$4<=R,C<=20。
$100\%$100%的数据， $4 <= R , C <= 75$4<=R,C<=75。

思路

由于$R$R和$C$C都不大，我们可以枚举横切法。
接着，我们二分答案，看以它为答案竖切是否能切到三道。
最后，我们求出每一种横切法的答案的最大值，就是答案了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=80;
int n,m,a[N][N],lim,ans;
bool check(int c1,int c2,int c3,int x)//判断能切多少块
{
	int p1=0,p2=0,p3=0,p4=0,k=0;
	for(int i=1;i<=n;i++){
		p1+=a[i][c1];
		p2+=a[i][c2]-a[i][c1];
		p3+=a[i][c3]-a[i][c2];
		p4+=a[i][m]-a[i][c3];
		if(p1>=x&&p2>=x&&p3>=x&&p4>=x)
			p1=p2=p3=p4=0,k++;
	}
	return k>=4;
}
int main()
{
	scanf("%d%d",&n,&m);//读入
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%1d",&a[i][j]);//读入
			lim+=a[i][j];//求出答案最大的答案
			a[i][j]+=a[i][j-1];//前缀和
		}
	for(int c1=1;c1<=m;c1++)
		for(int c2=c1+1;c2<=m;c2++)
			for(int c3=c2+1;c3<=m;c3++){//枚举横切法
				int l=0,r=lim;
				while(l<=r){//二分
					int mid=(l+r)/2;
					if(check(c1,c2,c3,mid)) l=mid+1;
					else r=mid-1;
				}
				ans=max(ans,r); //求出答案
			}
	printf("%d",ans);//输出
}