uva 10911 - Forming Quiz Teams(记忆化搜索)
题目链接：10911 - Forming Quiz Teams
题目大意：给出2 * n个选手的坐标， 要求将所有的选手分成n组， 每组两个人， 所有组的两个人之间的距离之和要最小， 输出最小值。
解题思路：网络赛的时候写过类似的题目， 只不过是选4个点做正方形，所以思路很明确，每次选取任意两个点配对，递归搜索，并记录下来。然后我不是用未运算来记录点的状态，而开了个数组，因为位运算用不熟。
#include <stdio.h>#include <string.h>#include <math.h>const int N = 20;const int MAX = 1 << 20;struct state {int x;int y;}tmp[N];int n, vis[N];double dis[MAX];void read() {char name[N];memset(dis, 0, sizeof(dis));memset(tmp, 0, sizeof(tmp));n = n * 2;for (int i = 0; i < n; i++) {scanf("%s%d%d", name, &tmp[i].x, &tmp[i].y);vis[i] = 1;}}int change() {int sum = 0;for (int i = 0; i < n; i++)sum = sum * 2 + vis[i];return sum;}double dist(int a, int b) {return sqrt( pow(tmp[a].x - tmp[b].x, 2) + pow(tmp[a].y - tmp[b].y, 2));}double solve() {int num = change();if (num == 0) return 0;if (dis[num] > 1e-9) return dis[num];double& sum = dis[num];sum = MAX;for (int i = 0; i < n; i++) {if (!vis[i]) continue;for (int j = i + 1; j < n; j++) {if (!vis[j]) continue;vis[i] = vis[j] = 0;double p = dist(i, j) + solve();if (p - sum < 1e-9) sum = p;vis[i] = vis[j] = 1;}}return sum;}int main() {int cas = 1;while (scanf("%d", &n), n) {read();printf("Case %d: %.2lf\n", cas++, solve());}return 0;}