在空间中的n（n为偶数）个点，，配成n对，然后使得每一个点在一个点对中。所有的点对的距离之和最小
#include <cstdio>#include <iostream>#include <algorithm>#include <queue>#include <stack>#include <climits>#include <cstring>#include <cmath>#include <map>#include <set>#define INF 100000000using namespace std;int n;int x[1000];int y[1000];int d[1<< 21];int dist(int a,int b){return (x[a] – x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a] – y[b]);}int main(){while(cin >> n){for(int i = 0;i < n;i++){cin >> x[i] >> y[i];}memset(d,0,sizeof(d));for(int i = 0;i < (1<<n);i++){d[i] = INF;}d[0] = 0;//依次枚举不同的集合for(int s = 0;s < (1<<n);s++){int i,j;//d[s] = min(|PiPj| + d[s-{i}-{j}]);for(i = 0;i < n;i++){ //枚举其中一个点if(s & (1 << i)) break;}for(j = i+1;j < n;j++){ //再找另外一个点if(s & (1 << j)){//比较去掉这两个点的集合最小值的方法d[s] = min(d[s],dist(i,j)+d[s^(1<<i)^(1<<j)]);}}}printf("%d\n",d[(1 << n)-1]);} return 0;}觉得的状态压缩dp适合于n较小但是状态异常复杂的dp环境
哪里有意志存在，哪里就会有出路。
