1
22
2016
0

【枚举+二分】BZOJ 3061: [Usaco2013 Feb]Partitioning the Farm

大家好我又回来颓了。

期末受寒潮影响考完语文政治暂停五天复(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

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;
}

 

Category: BZOJ | Tags: 二分 枚举 | Read Count: 323

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com