狀態壓縮dp 最優配對問題
來源：程序員人生 發布時間：2015-06-25 08:54:22 閱讀次數：3468次
在空間中的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環境
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
