题解 P4661 【[BalticOI 2008]网格】

yuzhechuan · 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);
}