题目链接: 点击进入 这个题n最大的时候只有8,但是直接暴力dfs的话还是会超时的,所以我们采用记忆化搜索的思路.要记忆化搜索就要找到一个合适的方法来表示当前的状态.对这个题恰好可以用一个n位的二进制表示,开始的时候都为1表示没有人配对;状态转移就是每次选择两个没配对的配对,并且将二进制数的对应位置0.
代码如下:
;{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;}
，乐观者在灾祸中看到机会;悲观者在机会中看到灾祸
