记录编号	337677	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2526.__围栏问题	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2016-11-04 19:18:37	内存使用	4.79 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

int m,k,n,x[20],y[20],f[17][1<<16],cost[1<<16],s[20],ans;

void dfs(int now,int cnt,int res)
{
	if (now==n)
	{
		if (res<ans) ans=res;
		return;
	}
	if (res+(k-cnt)*4>=ans) return;
	for (int a=1;a<=cnt;a++)
	{
		int pres=s[a];
		s[a]|=(1<<now);
		dfs(now+1,cnt,res-cost[pres]+cost[s[a]]);
		s[a]^=(1<<now);
	}
	if (cnt<k)
	{
		cnt++;
		s[cnt]=(1<<now);
		dfs(now+1,cnt,res+4);
	}
}

int main()
{
	freopen("xfence.in","r",stdin);
	freopen("xfence.out","w",stdout);

	scanf("%d%d%d",&m,&k,&n);
	for (int a=0;a<n;a++)
		scanf("%d%d",&x[a],&y[a]);
	if (n<=14)
	{
		memset(f,0x3f,sizeof(f));
		for (int a=1;a<(1<<n);a++)
		{
			int sx=1001,mx=-1,sy=1001,my=-1;
			for (int b=0;b<n;b++)
				if ((a>>b)&1)
				{
					if (x[b]<sx) sx=x[b];
					if (x[b]>mx) mx=x[b];
					if (y[b]<sy) sy=y[b];
					if (y[b]>my) my=y[b];
				}
			f[1][a]=(mx-sx+1)*2+(my-sy+1)*2;
		}
		for (int a=2;a<=k;a++)
			for (int b=0;b<(1<<n);b++)
				for (int c=b-1;c;c=(c-1)&b)
					f[a][b]=min(f[a][b],f[a-1][c]+f[1][b^c]);
		int ans=f[1][(1<<n)-1];
		for (int a=2;a<=k;a++)
			ans=min(ans,f[a][(1<<n)-1]);
		printf("%d\n",ans);
	}
	else
	{
		ans=4000;
		for (int a=1;a<(1<<n);a++)
		{
			int sx=1001,mx=-1,sy=1001,my=-1;
			for (int b=0;b<n;b++)
				if ((a>>b)&1)
				{
					if (x[b]<sx) sx=x[b];
					if (x[b]>mx) mx=x[b];
					if (y[b]<sy) sy=y[b];
					if (y[b]>my) my=y[b];
				}
			cost[a]=(mx-sx+1)*2+(my-sy+1)*2;
		}
		dfs(0,0,0);
		printf("%d\n",ans);
	}

	return 0;
}