记录编号	337398	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__围栏问题	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	8.512 s
提交时间	2016-11-04 13:15:10	内存使用	4.56 MiB

#include <iostream>
#include <cstring>
#include <cstdio>

//#include <ctime>

using namespace std;
const int N=17,INF=10000;
int n,m,k,x[N],y[N];
int dp[1<<16][17];
int x1,y1,x2,y2;
int main(){
  freopen("xfence.in","r",stdin);
  freopen("xfence.out","w",stdout);
  scanf("%d%d%d",&m,&k,&n);
  for(register int i=1;i<=n;i++)
    scanf("%d%d",&x[i],&y[i]);
  memset(dp,63,sizeof(dp));
  for(register int s=0;s<1<<n;s++){
    x1=INF,y1=INF;
    x2=-INF,y2=-INF;
    for(register int i=1;i<=n;i++)
      if((s>>(i-1))&1){
	x1=min(x1,x[i]);
	y1=min(y1,y[i]);
	x2=max(x2,x[i]);
	y2=max(y2,y[i]);
      }
    dp[s][1]=2*(x2-x1+y2-y1+2);
  }memset(dp[0],0,sizeof(dp[0]));
  //printf("%.3f\n",1.0*clock()/CLOCKS_PER_SEC);
  for(register int s=0;s<1<<n;s++){
    for(register int p=s-1;~p;p--){
      p&=s;
      for(register int t=2;t<=k;t++)
	if(dp[s][t]>dp[p][1]+dp[s^p][t-1])
	  dp[s][t]=dp[p][1]+dp[s^p][t-1];
    }
  }
  printf("%d\n",dp[(1<<n)-1][k]);
  //printf("%.3f\n",1.0*clock()/CLOCKS_PER_SEC);
  return 0;
}