UVA 10911 Forming Quiz Teams

대의: 가장 좋은 배합 문제, 집합상의 동태적 계획.
생각: 내가 한참을 하고 BUG를 한참을 찾았는데 LYJ의 백서에 오류가 있는 것 같아. 자고 싶으면 많이 이해해야 돼.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1<<21;
const int INF = 0x3f3f3f3f;

int n;

struct node
{
	int x, y;
}a[MAXN];

double d[MAXN];

double dist(node a, node b)
{
	double ans = sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
	return ans;
}

void read_case()
{
	n *= 2;
	for(int i = 0; i < n; i++) scanf("%*s %d %d", &a[i].x, &a[i].y);
}

void dp()
{
	d[0] = 0;
	for(int S = 1; S < (1<<n); S++)
	{
		int i, j;
		d[S] = INF;
		for(i = 0; i < n; i++) if(S & (1<<i)) break;
		for(j = i+1; j < n; j++) if(S & (1<<j))
		{
			d[S] = min(d[S], dist(a[i], a[j]) + d[S^(1<<i)^(1<<j)]);
		}
	}
	printf("%.2lf
", d[(1<<n)-1]);
}

void solve()
{
	read_case();
	dp();
}

int main()
{
	int times = 0;
	while(scanf("%d", &n) && n)
	{
		printf("Case %d: ", ++times);
		solve();
	}
	return 0;
}