题意
经典模型“最优配对问题”,给出了平面上若干个点,你要把牠们两两配对,使得每一对中两点距离之和最小。
思路
分析问题:我们发现,本问题可以着眼于“最后一次配对”,是一个多阶段决策。不妨考虑当最后一次选择拿i号点去和j号点去配对,得到了某种状态时可以得到的最优解。
状态表示:dp[当前状态下各个点是否已经配对][最后一次配对的点i][最后一次配对的点j]
我们发现这个状态设的太繁了,假如我们要配对a和b这两个点,那么在所有的配对状态里面都要算入a和b的距离,在所有没配对状态里都不可以算入a和b的距离,后两个维度强行决定了一组点的配对情况,然而并没有什么意义,因为后两个维度的信息已经包括进了第一个维度里,我们只要想办法让第一个维度可以表达出决策的“分阶段”特性,能够识别出最后一步是什么就可以。
于是我们重设状态:dp[当前状态下各个点是否已经配对]并且规定在每个状态中,最低位为1对应的那个点是我们最后一次操作的点。
这样有状态转移:dp[S] = min{dis(i,j) + dp[S^i^j]} 在这里S是二进制表示的状态,i,j是假定的最后一次配对的点对,其中规定i一定是S中最低位的那个点,dis表示求距离,S^i^j表示将二进制表示的状态中i,j对应的位设成零之后得到的二进制状态
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cstdio> using namespace std; int n; struct Student{ double x; double y; string name; } stu[17]; double dis(Student &a,Student &b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double dp[17][100000]; double solve(){ memset(dp, 0x77, sizeof(dp)); dp[0][0] = 0; dp[1][0] = 0; dp[1][1] = 0; for(int i = 2;i <= n; i++){ for(int j = 0; j < (1 << i) ;j++){ if(j&(1 << (i-1))){ for(int k = 1; k < i; k++){ if(j & (1 << (k-1))){ dp[i][j] = min(dp[i][j],dp[i-1][j^(1 << (i-1))^(1 << (k-1))] + dis(stu[i], stu[k])); } } }else{ dp[i][j] = dp[i-1][j]; } } } return dp[n][(1 << n)-1]; } int main(){ int caseCnt = 0; while(cin >> n){ if(!n){ break; } n *= 2; caseCnt++; for(int i = 1; i <= n; i++){ cin >> stu[i].name >> stu[i].x >> stu[i].y; } cout << "Case " << caseCnt << ": " << fixed << setprecision(2) << solve() << endl; } return 0; } |