大家好我又回来颓了。
期末受寒潮影响考完语文政治暂停五天复(kuang)习(huan)，回去继续考(bao)试(ling)
3061: [Usaco2013 Feb]Partitioning the Farm
Time Limit: 10 Sec Memory Limit: 128 MB
Description
FJ的农场是n*n(2<=n<=15)的，每块地里有若干头牛，FJ最多能建K(1<=k<=2n-2)条篱笆，而这些篱笆只能沿着每块地的边缘建。建完篱笆之后，牛被分成了若干群。FJ想使得这些群中牛最多的那个群的牛尽量少。请输出满足FJ要求的情况下的牛最多的那个群有多少头牛。
Input
* Line 1: Two integers, N and K * Lines 2..1+N: There are N numbers per line, describing the cows in each pasture for one row of the farm (there are at least 0 and at most 1000 cows in each pasture)
Output
Line 1: The minimum possible size of the largest group of cows.
Sample Input
3 2
1 1 2
1 1 2
2 2 4
1 1 2
1 1 2
2 2 4
Sample Output
4
一眼枚举+二分。
状压暴枚横向栅栏，二分答案，扫描判断竖向是否资磁。
就写写写颓颓颓= =
Code：
#include<cstdio>
int a[16][16],s[16][16],n,k,F[16],L,R,ANS=1<<30,i,j,l,r,ALL,S,ll,rr,ans,mid,W,p,f;
int check(const int &x,int w)
{
r=k-w,l=0,F[++w]=n;
for(i=1;i<=n;++i)
{
for(j=1;j<=w;++j)if(s[i][F[j]]-s[i][F[j-1]]-s[l][F[j]]+s[l][F[j-1]]>x){l=i-1;i--;r--;break;}
if (r<0)return 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
scanf("%d",&a[i][j]),s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j],L=L>a[i][j]?L:a[i][j];
R=s[n][n];if(L==R)ANS=0;
ALL=1<<n-1;
for (S=0;S<ALL;++S)
{
W=0,p=0,f=S;
for(i=1;i<=n-1;++i,f>>=1)if(f&1)F[++W]=i;
if (W>k||k-W>=n)continue;
ll=L,rr=R;
while(ll<rr)
{
mid=ll+rr>>1;
if(check(mid,W))ans=mid,rr=mid;
else ll=mid+1;
}
if(ans<ANS)ANS=ans;
}
printf("%d",ANS);
return 0;
}
评论 (0)
