自动搬运

查看原文

来自洛谷，原作者为

	yuzhechuan **

搬运于2025-08-24 22:02:24，当前版本为作者最后更新于2020-07-25 00:02:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做的人真少，数据挺强，但并不卡时间，轻松最优解

题解：

套路题，对于一维（我是纵）暴力枚举状态是否切开，对于另一维二分答案后贪心的切，看看段数够不够就好了

代码：

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=20;
int ans=INT_MAX,mp[N][N],pre[N][N],cur[N],n,m,a,b,sum;

int count(int x){
	int res=0;
	while(x) res++,x^=x&(-x);
	return res;
}

bool check(int mid){
	int cnt=0;
	for(int i=0;i<=b;i++) cur[i]=0;
	for(int i=0;i<n;i++){
		bool flag=0;
		for(int j=0;j<=b;j++){
			cur[j]+=pre[j][i];
			if(cur[j]>mid){ //需要多切一刀
				flag=1;
				break;
			}	
		}
		if(!flag) continue;
		if(++cnt>a) return 0; //不够切
		for(int j=0;j<=b;j++) cur[j]=pre[j][i]; //重新开始
	}
	return 1;
}

signed main(){
	read(n,m,a,b);
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) sum+=read(mp[i][j]);
	for(int s=0;s<(1<<m-1);s++) if(count(s)==b){ //状态为1则表示当前列为一个块的起始列
		s=s<<1|1;
		for(int i=0;i<=b;i++) for(int j=0;j<n;j++) pre[i][j]=0;
		int l=0,r=sum,res=sum,id=-1;
		for(int i=0;i<m;i++){
			if(s>>i&1) id++;
			for(int j=0;j<n;j++) pre[id][j]+=mp[j][i],l=max(l,pre[id][j]);
		}
		while(l<=r){
			int mid=l+r>>1;
			if(check(mid)) res=mid,r=mid-1;
			else l=mid+1;
		}
		ans=min(ans,res);
		s>>=1;
	}
	write(ans);
}