UVA 10911-Forming Quiz Teams+状态压缩+记忆化搜寻

题目链接: 点击进入
这个题n最大的时候只有8,但是直接暴力dfs的话还是会超时的,所以我们采用记忆化搜索的思路.要记忆化搜索就要找到一个合适的方法来表示当前的状态.对这个题恰好可以用一个n位的二进制表示,开始的时候都为1表示没有人配对;状态转移就是每次选择两个没配对的配对,并且将二进制数的对应位置0.

代码如下:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

#define maxn 1100000
#define INF (1e30*1.0)

typedef struct
{
    double x, y;
}P;
P p[20];

double d[maxn];
double m[22][22];
int n;

double dist(int i,int j)
{
     double xx=(p[i].x-p[j].x)*(p[i].x-p[j].x);
     double yy=(p[i].y-p[j].y)*(p[i].y-p[j].y);
     return sqrt(xx+yy);
}

double dp(int s)
{
     if(d[s]!=-1)
        return d[s];
     d[s]=INF;
     for(int i=0;i<n;i++)
     {
          if(s&(1<<i)) ///为1说明当前编号还未配对
         {
              for(int j=0;j<n;j++)  ///状态转移就是选两个还未配对的配对
                  if((i!=j)&&(s&(1<<j)))
                  {
                        d[s]=min(d[s],dp(s^(1<<i)^(1<<j))+m[i][j]);
                  }
         }
     }
     return d[s];
}

int main()
{
     //freopen("in.txt","r",stdin);
     int Case=0;
      while(scanf("%d",&n)&&n)
      {
            n*=2;
            char str[110];
            for(int i=0;i<n;i++)
                 scanf("%s%lf%lf",str,&p[i].x,&p[i].y);
            for(int i=0;i<n;i++)
               for(int j=0;j<n;j++)
                    m[i][j]=dist(i,j);
            int s=(1<<n)-1;  ///用n位全为1的二进制数表示每个人的配对情况
            for(int i=0;i<=s;i++)
               d[i]=-1;
            d[0]=0;
            dp(s);
            printf("Case %d: %.2lf\n",++Case,d[s]);
      }
    return 0;
}