本文主要是介绍UVA 10911 Forming Quiz Teams(dp + 集合最优配对问题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 4th IIUC Inter-University Programming Contest, 2005 | |
| G | Forming Quiz Teams |
| Input: standard input | |
| Problemsetter: Sohel Hafiz | |
You have been given the job of forming the quiz teams for the next ‘MCA CPCI Quiz Championship’. There are2*N students interested to participate and you have to form N teams, each team consisting of two members. Since the members have to practice together, all the students want their member’s house as near as possible. Let x1 be the distance between the houses of group 1, x2 be the distance between the houses of group 2 and so on. You have to make sure the summation (x1 + x2 + x3 + …. + xn) is minimized.
Input
There will be many cases in the input file. Each case starts with an integer N (N ≤ 8). The next 2*Nlines will given the information of the students. Each line starts with the student’s name, followed by thex coordinate and then the y coordinate. Both x, y are integers in the range 0 to 1000. Students name will consist of lowercase letters only and the length will be at most 20.
Input is terminated by a case where N is equal to 0.
Output
For each case, output the case number followed by the summation of the distances, rounded to 2 decimal places. Follow the sample for exact format.
| Sample Input | Output for Sample Input |
| 5 | Case 1: 118.40 |
思路：明显的集合最优配对问题，i最为前i个人，s作为前i个人能组成的所有集合。j为前i个人中的一个人
这样状态转移方程为dp[i][s] =min(dp[i][s], dis(i, j) + dp[i - 1][s - {i} - {j}]。集合用二进制来表示。所以方程变为
dp[i][s] =min(dp[i][s], dis(i, j) + dp[i - 1][s ^ 1<<i ^ 1<<j]。但是这样做时间不是很理想。然后看了个详细解法
http://blog.csdn.net/accelerator_/article/details/11181905
里面讲得挺详细的。可以转化为1维。
代码：
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>int n, i, j, s;
double dp[1<<20];
struct Student{char name[105];int x, y;
} stu[20];double min(double a, double b) {return a < b ? a : b;
}double dis(Student a, Student b) {return sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}double dpp(int p) {if (dp[p] != -1) return dp[p];dp[p] = INT_MAX;int i, j;for (i = n - 1; i >= 0; i --)if (p & (1 << i))break;for (j = i - 1; j >= 0; j --)if (p & (1 << j))dp[p] = min(dp[p], dis(stu[i], stu[j]) + dpp(p ^ (1<<i) ^ (1<<j)));return dp[p];
}
int main(){int t = 1;while (~scanf("%d", &n) && n) {n *= 2;s = 1<<n;for (i = 1; i < s; i ++)dp[i] = -1;dp[0] = 0;for (i = 0; i < n; i ++)scanf("%s%d%d", stu[i].name, &stu[i].x, &stu[i].y);printf("Case %d: %.2lf\n", t ++, dpp(s - 1));}return 0;
}
这篇关于UVA 10911 Forming Quiz Teams(dp + 集合最优配对问题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
