【NOIP2016模拟测试】dan

发布于 2016-11-14  375 次阅读


Description

m*m的方阵上有n棵葱,你要修一些栅栏把它们围起来。一个栅栏是一段沿着网格建造的封闭图形(即要围成一圈)。各个栅栏之间应该不相交、不重叠且互相不包含。如果你最多修k个栅栏,那么所有栅栏的长度之和最小是多少?

Input Format

第一行三个整数m,k,n。 接下来行每行两个整数x,y代表某棵葱的位置。

Output Format

一行一个整数代表答案

Sample Input

6 1 4
1 3
4 2
4 4
6 4

Sample Output

18

题目分析:本来是一题状压,貌似搜索更快,裸的dfs直接就过了..分三种情况:1.包含在已知区间内,不选,直接dfs下一个节点。否则  2.在已知区间内枚举进行答案的更新 3.新开一个区间。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;

struct info{
	int xl,xr,yl,yr;
}mat[20]; 
struct point{
	int x,y;
}p[20];
int k,n,m,ans;
inline void dfs(int now,int num,int tot){
	if (num>k) return ;
	if (now>m){
		ans=min(ans,tot);
		return ;
	}
	bool flag=0;
	For (i,num){
		if (mat[i].xl<=p[now].x&&mat[i].xr>=p[now].x&&mat[i].yl<=p[now].y&&mat[i].yr>=p[now].y){
			flag=1;break;
		}
	}
	if (flag) dfs(now+1,num,tot);else {
		For (i,num){
			info tmp=mat[i];
			tot-=(tmp.xr-tmp.xl+1)*2+(tmp.yr-tmp.yl+1)*2;
			mat[i].xl=min(mat[i].xl,p[now].x);
			mat[i].xr=max(mat[i].xr,p[now].x);
			mat[i].yl=min(mat[i].yl,p[now].y);
			mat[i].yr=max(mat[i].yr,p[now].y);
			tot+=(mat[i].xr-mat[i].xl+1)*2+(mat[i].yr-mat[i].yl+1)*2;
			if (tot<ans) dfs(now+1,num,tot);
			tot-=(mat[i].xr-mat[i].xl+1)*2+(mat[i].yr-mat[i].yl+1)*2;
			tot+=(tmp.xr-tmp.xl+1)*2+(tmp.yr-tmp.yl+1)*2;
			mat[i]=tmp;
		}
		mat[num+1].xl=mat[num+1].xr=p[now].x;
		mat[num+1].yl=mat[num+1].yr=p[now].y;
		dfs(now+1,num+1,tot+4);
	}
}

int main(){
	scanf("%d%d%d",&n,&k,&m);
	For (i,m){
		scanf("%d%d",&p[i].x,&p[i].y);
	}
	ans=INF;
	dfs(1,0,0);
	printf("%d",ans);
}

「知我罪我,其惟春秋」