UVa 10911 - Forming Quiz Teams 상태 압축 dp
G
Forming Quiz Teams
Input: standard input Output: standard output
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 sohel 10 10 mahmud 20 10 sanny 5 5 prince 1 1 per 120 3 mf 6 6 kugel 50 60 joey 3 24 limon 6 9 manzoor 0 0 1 derek 9 9 jimmy 10 10 0
Case 1: 118.40 Case 2: 1.41
------------------------------
상태 압축 dp, 직접 dp보다 기억화 검색이 빠른 것 같은데, dp는 0.132ms, 기억화 검색은 0.032ms만 사용했습니다.
f[x]=min(f[x^(1-----------------------------
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double OO=1e17;
struct STU{
int x;
int y;
}stu[32];
double a[32][32];
int n;
char s[111];
double f[1<<17];
bool v[1<<17];
int lowbit(int x)
{
return x&(-x);
}
double dfs(int x)
{
int i,j;
double ret=OO;
if (v[x]) return f[x];
for (i=0;i<n;i++)
{
if (x&(1<<i)) break;
}
for (j=i+1;j<n;j++)
{
if (x&(1<<j))
{
ret=min( ret, dfs(x^(1<<i)^(1<<j))+a[i][j] );
}
}
f[x]=ret;
v[x]=true;
return ret;
}
void DP()
{
int i,j,x;
for (i=0;i<(1<<n);i++) f[i]=OO;
f[0]=0;
for (x=1;x<(1<<n);x++)
{
for (i=0;i<n;i++)
{
if (x&(1<<i)) break;
}
for (j=i+1;j<n;j++)
{
if (x&(1<<j))
{
f[x]=min( f[x], f[x^(1<<i)^(1<<j)]+a[i][j] );
}
}
}
printf("%0.2lf
",f[(1<<n)-1]);
}
int main()
{
int cnt=1;
while (~scanf("%d",&n))
{
if (n==0) break;
memset(f,0,sizeof(f));
memset(v,0,sizeof(v));
n*=2;
for (int i=0;i<n;i++)
{
scanf("%s%d%d",s,&stu[i].x,&stu[i].y);
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
a[i][j]=sqrt((stu[i].x-stu[j].x)*(stu[i].x-stu[j].x)+(stu[i].y-stu[j].y)*(stu[i].y-stu[j].y));
}
}
printf("Case %d: ",cnt++);
//DP();
v[0]=true;
double ans=dfs((1<<n)-1);
printf("%0.2lf
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.