状态压缩dp 最优配对问题

#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <climits> #include <cstring> #include <cmath> #include <map> #include <set> #define INF 100000000 using 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++){ //枚举其中1个点 if(s & (1 << i)) break; } for(j = i+1;j < n;j++){ //再找另外1个点 if(s & (1 << j)){ //比较去掉这两个点的集合最小值的方法 d[s] = min(d[s],dist(i,j)+d[s^(1<<i)^(1<<j)]); } } } printf("%d ",d[(1 << n)⑴]); } return 0; }