题解 P3075 【[USACO13FEB]分区的农场Partitioning the Farm】

巨型方块 · 2017-10-18 22:11:02 · 题解

先二分答案嘛

然后我判断这个答案嘛

一看范围这么小嘛

那么我们爆搜i坐标，看在哪里分割；

再贪心得顺推j

在J上面尽可能少的划分

如果i的划分和j的划分结果>m

那就不行

i的搜索么直接大力压位

#include<bits/stdc++.h>
#define Ll long long
using namespace std;
const int N=16;
int a[N][N],b[N][N],c[N][N];
bool ne[N];
int n,m,t;
bool check(int k,int v){
    int top=1,o;memset(c,0,sizeof c);
    for(int i=1;i<=n;i++){
        if(i>1&&((k>>(i-2))&1))top++;
        for(int j=1;j<=n;j++)c[top][j]+=b[i][j];        
    }
    if(top>m+1)return 0;o=m-top+1;
    for(int l=0,r=1;r<=n;r++)
        for(int i=1;i<=top;i++)
            if(c[i][r]-c[i][r-1]>v)return 0;else 
                if(c[i][r]-c[i][l]>v)l=r-1,o--;
    if(o<0)return 0;return 1;
}
int main()
{
    int l=0,r=0,mid,ans;bool ok;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),r+=a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)b[i][j]=b[i][j-1]+a[i][j];
    t=(1<<(n-1));
    while(r>=l){
        mid=l+r>>1;ok=0;
        for(int i=0;i<t;i++)
            if(check(i,mid)){ok=1;break;}
        if(ok)ans=mid,r=mid-1;else l=mid+1;
    }
    printf("%d",ans);
}
但是这道题有一个更快的方法，可惜看不了别人代码，不知道怎么做，大家不妨想一想