首页 > 代码库 > uva10911 - Forming Quiz Teams(记忆化搜索)
uva10911 - Forming Quiz Teams(记忆化搜索)
题目:uva10911 - Forming Quiz Teams(记忆化搜索)
题目大意:给出N对点的坐标,然后将这2 * N个点分组,Xi代表第i组的点之间的距离,求sum(Xi)最小值。
解题思路:这里的点最多16个,如果暴力求解的话16!,会超时的。这里的点取和不取可以用0和1表示,这样的话所有的状态可以用二进制数X来表示。dp【X】 = Min (dp【newx】 + d【i】【j】);记录下状态来减少不必要的重复操作。
i 、j代表点的下标,这些点必须是X状态下没取过的,newx就是加上这两个点的新状态的二进制。
代码:
#include <cstdio> #include <cstring> #include <cmath> const int N = 20; const int maxn = 1 << N; const double esp = 10005; int member[N][2]; double dist[maxn]; double d[N][N]; char name[N + 5]; int n; double Min (const double a, const double b) { return a < b ? a: b; } double distance (int i, int j) { double x = member[i][0] - member[j][0]; double y = member[i][1] - member[j][1]; return sqrt (x * x + y * y); } double dfs (int s) { int news; double& ans = dist[s]; if (ans != esp) return ans; if (s == (1 << (2 * n)) - 1) return 0; for (int i = 0; i < 2 * n; i++) for (int j = i + 1; j < 2 * n; j++) { if ((s & (1 << i)) || (s & (1 << j))) continue; news = (s | (1 << i)) | (1 << j); // printf ("%d\n", news); ans = Min (ans, dfs (news) + d[i][j]); } return ans; } void init () { for (int i = 0; i < 1 << (2 * n); i++) dist[i] = esp; // printf ("%lf\n", dist[0]); for (int i = 0; i < 2 * n; i++) for (int j = i + 1; j < 2 * n; j++) { d[i][j] = d[j][i] = distance(i, j); // printf ("%lf\n", d[i][j]); } } int main () { int cas = 0; while (scanf ("%d", &n), n) { for (int i = 0; i < 2 * n; i++) scanf ("%s%d%d", name, &member[i][0], &member[i][1]); init(); printf ("Case %d: %.2lf\n", ++cas, dfs(0)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。