状态压缩dp 最优配对问题
来源：程序员人生 发布时间：2015-06-25 08:54:22 阅读次数：3296次
在空间中的n（n为偶数）个点，配成n对，然后使得每个点在1个点对中。所有的点对的距离之和最小
#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;
}
觉得的状态紧缩dp合适于n较小但是状态异常复杂的dp环境
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
