最优配对问题：空间里有n个点P0,P1,…,Pn-1，你的任务是把它们配成n/2对（n是偶数），使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。 

紫书：P284.还有就是刘汝佳为数不多的一个小错误，max (应该是min)

到网上逛了一下，果然是个经典问题。首先就是关于集合的任意子集的表示，dp的思路。

我这里写了两种方法，编译不了，只不过是 dp 重命名了，主要是记录这个思想。

dp方程：

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

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

集合的表示，之前我在一道最小生成树的枚举上用过，可以借鉴到这里来，怎么找 j 呢？ 集合 S 和 j 是否有交集 (S&(1<<j)) ，出去 i j 的集合怎么表示呢？ d[i-1][S^(1<<i)^(1<<j)];

这就是第一种方式。

第二种方式：

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

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

 

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

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

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

 

#include 
     
      using namespace std;///最优配对问题#define maxnode 5000#define maxnodes 5000<<1#define INF 0x3f3f3f3fint d[maxnode][maxnodes];int n;  ///点的个数int main(){    ///结果存在 d[n-1][(1<