C++之动态规划配对算法

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <vector> #include <cmath> #include <map> using namespace std; #define LL long long const int N = 29; int x[N], y[N], z[N]; double dist[N][N]; double dp[(1<<N)]; void init_dist(int n) { for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) dist[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j]) +(y[i]-y[j])*(y[i]-y[j]) +(z[i]-z[j])*(z[i]-z[j])); } double solve(int n) { for(int s=1; s<(1<<n); s++) { dp[s] = 1E9; int pos = 0; while(pos<n && !(s&(1<<pos))) ++pos; for(int i=pos+1; i<n; i++) if(s&(1<<i)) dp[s] = min(dp[s], dist[pos][i]+dp[s^(1<<pos)^(1<<i)]); } return dp[(1<<n)-1]; } int main() { int n; cin>>n; for(int i=0; i<n; i++) cin>>x[i]>>y[i]>>z[i]; init_dist(n); dp[0] = 0; cout<<solve(n)<<endl; return 0; }