点集配对问题(状态dp)
给定n个点(n是偶数)使得两个点两两配对,最后总的距离和最小。
用是表示集合,那么dp[s]表示集合s配对后的最小距离和 ,
状态转换方程为
表示集合中任意拿两个元素配对,然后转移为更小的两个集合的点集配对。i=min(s)表示i为集合中的第一个元素,因为第一个元素肯定要配对的,
所以找到集合中的第一个元素后,我们枚举要配对的另外一个元素j,j>i && j属于s
我们用二进制表示一个集合,1表示该元素存在,0表示不存在,然后进行状态转移
我们不需要担心一个状态的子状态没有被算出来,
因为一个状态的子状态总是比该状态来的小,所以肯定会被先算出来
比如状态(1111)2 的子状态(1001)2, (1100)2……肯定都是被算出来了
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 const int N = 1000 + 10; 18 /* 19 给定n(n是偶数)个点,把它们配乘n/2对,使得总的距离和尽量小 20 */ 21 struct Point 22 { 23 double x, y; 24 double dist(const Point &rhs) 25 { 26 return sqrt((x - rhs.x)*(x - rhs.x) + (y - rhs.y)*(y - rhs.y)); 27 } 28 }a[N]; 29 double dp[N]; 30 void solve(int n) 31 { 32 int m = 1 << n; 33 int i, j, s; 34 for (i = 1; i < m; ++i) 35 dp[i] = INF; 36 dp[0] = 0; 37 for (s = 0; s < m; ++s)//集合为是s 38 { 39 for (i = 0; i < n; ++i)//找出集合中的第一个元素i 40 { 41 if (s&(1 << i)) 42 break; 43 } 44 for (j = i + 1; j < n; ++j)//在集合中找到另一个元素j与之配对 45 { 46 if (s&(1 << j)) 47 { 48 dp[s] = min(dp[s], dp[s ^ (1 << i) ^ (1 << j)] +a[i].dist(a[j])); 49 } 50 } 51 } 52 } 53 int main() 54 { 55 int n, i; 56 while (scanf("%d", &n) != EOF) 57 { 58 for (i = 0; i < n; ++i) 59 scanf("%lf%lf", &a[i].x, &a[i].y); 60 solve(n); 61 cout << dp[(1 << n) - 1] << endl; 62 } 63 return 0; 64 }
View Code