记录编号	337905	评测结果	AAAAAATTTTTTTTTTTTTT
题目名称	__围栏问题	最终得分	30
用户昵称	Riolu	是否通过	未通过
代码语言	C++	运行时间	42.134 s
提交时间	2016-11-04 22:06:20	内存使用	3.94 MiB

/*=========================================*
  * Auther: Riolu
  * Time: 2016.11.4
  * ©Copyright 2016 Riolu. All Rights Reserved.
  *=========================================*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const int N =1001;

int n,m,k;
int e[N][N];
P rb[20],rb2[20];
int xx[N],yy[N];
bool tx[N],ty[N];

int dfs(int x1,int y1,int x2,int y2,int k){
	int i,j;
	if(x1>x2||y1>y2)return 0;
	if(k==1){
		int pos=0;
		for(i=x1;i<=x2;i++) for(j=y1;j<=y2;j++)
			if(e[i][j]){
				rb[pos]=P(i,j);
				rb2[pos++]=P(j,i);
			}
		
		sort(rb,rb+pos);
		sort(rb2,rb2+pos);
		
		int tt=(rb[pos-1].first-rb[0].first+rb2[pos-1].first-rb2[0].first+2)*2;
		//cout<<tt<<endl;
		if(pos==0) return 0;
		
		if(tt<0){
			cout<<"WRONG:\n";
			cout<<pos<<endl;
			cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
			cout<<tt<<endl;
			cout<<rb[pos-1].first<<' '<<rb[0].first<<endl;
			cout<<rb2[pos-1].first<<' '<<rb2[0].first<<endl;
		}
		return (rb[pos-1].first-rb[0].first+rb2[pos-1].first-rb2[0].first+2)*2;
	}
	int ans=1e8;
	for(i=0;i<n;i++){
		if(xx[i]>x2)break;
		if(xx[i]>=x1)ans=min(dfs(x1,y1,xx[i],y2,1)+dfs(xx[i+1],y1,x2,y2,k-1),ans);
	}
	for(j=y1;j<=y2;j++){
		if(yy[j]>y2)break;
	  if(yy[j]>=y1)ans=min(dfs(x1,y1,x2,yy[j],1)+dfs(x1,yy[j+1],x2,y2,k-1),ans);
	}
	return ans;
}

int main(){
	freopen("xfence.in","r",stdin);
	freopen("xfence.out","w",stdout);
	int i,y,x;
	cin>>m>>k>>n;
	for(i=0;i<n;i++){
		cin>>x>>y;
		rb[i]=P(x,y);
		rb2[i]=P(y,x);
		xx[i]=9000;yy[i]=9000;
		if(!tx[x]){tx[x]=1;xx[i]=x;}
		if(!ty[y]){ty[y]=1;yy[i]=y;}
		e[x][y]=1;
	}
	sort(xx,xx+n);
	sort(yy,yy+n);
	
	//for(i=0;i<n;i++)cout<<xx[i]<<endl;
	//for(i=0;i<n;i++)cout<<yy[i]<<endl;
	
	if(k==1){
		sort(rb,rb+n);
		sort(rb2,rb2+n);
		cout<<(rb[n-1].first-rb[0].first+rb2[n-1].first-rb2[0].first+2)*2<<endl;
		return 0;
	}
	
	cout<<dfs(1,1,m,m,k)<<endl;
	
	return 0;
}
/*

*/