这题实在不懂你们可以查查博客http://www.cnblogs.com/TreeDream/p/6011865.html
http://blog.csdn.net/qq_26122039/article/details/50654319
http://blog.csdn.net/sinat_26019265/article/details/51291331

p方程：

d[i][S] 点0~i 的最优匹配，S为状态集合。

d[i][S] = min(d[i][j],dist(i,j)+d[i-1][S-{i}-{j}]);

集合的表示（二进制）， 集合 S 和 j 是否有交集 (S&(1<<j)) ，出去 i j 的集合怎么表示呢？ d[i-1][S^(1<<i)^(1<<j)];

这就是第一种方式。

第二种方式：

你可以发现， i 一定是 S中最大的元素，那么dp就可以减少一维。

d(S) = min(dis|PiPj| + d(S-{i}-{j})) | i = max(S);

但是，可以发现，找最小的是可以很容易找出来的，不如，将第一种的定义修改一下。

d[i][S] i ~ n 的点，状态集合是 S ，

那么循环顺序，就是 (j = i+1;j<n;j++) 了
程序如下：

include<cstdio>

include<cmath>

include<iostream>

using namespace std;
struct t
{
int x,y;
} a[21];
int i,j,k,n,sum;
double minn[(1<<20)-1],c[21][21];
double dis(int i,int j)

{

return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));

}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
c[i][j]=dis(i,j);
sum=(1<<n)-1;
for (k=1;k<=sum;k++)
{
minn[k]=10000007;
for (i=1;i<=n-1;i++)
if (k&(1<<(i-1))) break;
for (j=i+1;j<=n;j++)
if (k&(1<<(j-1)))
minn[k]=min(minn[k],minn[k^(1<<(i-1))^(1<<(j-1))]+c[i][j]);
}
printf("%.2f\n",minn[sum]);
return 0;
}