宝藏图 题解

题意简述

n x m 的方格图，先水平剪成A条，然后对于每一横条，竖直剪成B块，求一块宝藏价值最小值的最大值。

分析

二分答案（当前的x是否能 在满足题意的剪法下 作为最小价值的块）。

Warning

不一定要剪成网格状的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=507;
int n,m,A,B,ans,a[N][N],add[N][N];
int check(int x){
	int row=0,lst_row=0;//row:剪了几横行; lst_row:上次横剪的位置 
	for(int i = 1;i<=n;i++){
		int col=0,lst_col=0;//col:剪了几竖行; lst_col:上次竖剪的位置
		for(int j = 1;j<=m;j++){
			//other: i~lst_row j~lst_col 的块内的价值总和
			int other=add[i][j]-add[lst_row][j]-add[i][lst_col]+add[lst_row][lst_col];
			//要保证x是价值最小的块 
			if(other>=x)col++,lst_col=j;
		}
		if(col>=B)row++,lst_row=i;
	}
	return row>=A;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>A>>B;
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			cin>>a[i][j];
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			add[i][j]=add[i-1][j]+add[i][j-1]-add[i-1][j-1]+a[i][j];
	int l=1,r=add[n][m];
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<l<<'\n';
	return 0;
}