【问题描述】

? × ?的方阵上有?棵葱，你要修一些栅栏把它们围起来。一个栅栏是一段

沿着网格建造的封闭图形（即要围成一圈） 。各个栅栏之间应该不相交、不重叠

且互相不包含。如果你最多修?个栅栏，那么所有栅栏的长度之和最小是多少？

【输入格式】

第一行三个整数?,?,?。

接下来?行每行两个整数?,?代表某棵葱的位置。

【输出格式】

一行一个整数代表答案。

【样例输入 1】

6 1 4

1 3

4 2

4 4

6 4

【样例输出 1】

18

【样例输入 2】

6 2 4

1 3

4 2

4 4

6 4

【样例输出 2】

16

【样例解释】

你猜树上有啥，有钟神呗。

 

【数据规模与约定】

1= 1 32。

60%的数据，? ≤ 10。

对于100%的数据，1 ≤ ? ≤ ? ≤ 16,? ≤ 1000。

 

 

思路：

　　搜索+剪枝+卡时

　　但是，只有95分

　　作为蒟蒻的ac不过去了

　　写篇随笔然后继续下一题

　　搜索的话有两种

　　1.搜索每个栅栏放哪几根葱

　　2.搜索每根葱放在哪个栅栏里

　　先看第一种方法

　　搜索哪个栅栏放哪几根葱

　　这个方法不仅恶心而且麻烦还要记录多个状态

　　所以，果断放弃

　　第二种方法

　　一根葱对应着一个栅栏，只有这一种搜索状态

　　相比第一种方法无疑是一种非常简单且省事的方法

　　果断选择第二种

　　因为是要求最小的ans

　　所以唯一的一个剪枝就是

　　if(当前长度>=ans) return;

　　ans初始赋极大值

 

　　来，上代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct node {    int x,y;};struct node ci[1001];int n,k,m,ans=0x7fffff,up[20],down[20],l[20],r[20],pd[20];int max(int a,int b){
   return a>b?a:b;}int min(int a,int b){
   return a
         
          =down[i]&&ci[kcc].y<=r[i]&&ci[kcc].y>=l[i])            return true;        }    }    return false;}int lenth(){    int cur=0;    for(int i=1;i<=k;i++) if(pd[i]==1)        cur+=(down[i]-up[i]+1+r[i]-l[i]+1)*2;    return cur;}void dfs(int now){    if(clock()>=1980){        printf("%d\n",ans);        exit(0);    }    int cur=lenth();    if(cur>=ans) return ;    if(now==n+1)    {        ans=cur;        return ;    }    int iup,idown,il,ir;    for(int i=1;i<=k;i++)    {        if(check(i,now)) continue;        iup=up[i];        idown=down[i];        il=l[i];        ir=r[i];        up[i]=min(ci[now].x,up[i]);        down[i]=max(ci[now].x,down[i]);        l[i]=min(ci[now].y,l[i]);        r[i]=max(ci[now].y,r[i]);        if(pd[i]==0)        {            pd[i]=1;            dfs(now+1);            pd[i]=0;        }        else dfs(now+1);        up[i]=iup;        down[i]=idown;        l[i]=il;        r[i]=ir;    }}int main(){    scanf("%d%d%d",&m,&k,&n);    for(int i=1;i<=n;i++) scanf("%d%d",&ci[i].x,&ci[i].y);    memset(up,127/3,sizeof(up));    memset(down,-1,sizeof(down));    memset(l,127/3,sizeof(l));    memset(r,-1,sizeof(r));    dfs(1);    printf("%d\n",ans);    return 0;}