uva10911 - Forming Quiz Teams 컬렉션 DP
너에게 몇 가지를 줄게, 두 쌍의 짝을 요구하고, 이 짝의 거리와 최소치를 물어봐라.
d(i,S)는 앞의 i점에서 집합S에 있는 원소를 두 쌍으로 짝짓는 최소 거리를 표시하기 때문에 d(i,S)=min{|Pipj|+d(i-1,S-{i}-{j})|j는 S}에 속한다.
1은 이 점을 대표하고 0은 없다. 예를 들어 6개의 점 d[11111]가 바로 요구하는 답이다. 이것은 p[5][0]+d[011110], p[5][1]+d[011101], p[5][2]+d[011011], p[5][3]+d[010111], p[5][4]+d[001111]의 최소값이다.이때 서브문제만 요구하면 된다. 기억화 검색을 되돌릴 수도 있고 000001에서 1111111로 순환해서 모든 상태를 한 번 구할 수도 있다. 그러나 분명히 앞의 방법이 빠르다. 왜냐하면 홀수를 구하지 않아도 되기 때문이다.
You have been given the job of forming the quiz teams for the next ‘MCA CPCI Quiz Championship’. There are2*Nstudents interested to participate and you have to formN 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 integerN (N ≤ 8).The next2*N lines will given the information of the students. Each line starts with the student’s name, followed by thex coordinate and then they coordinate. Bothx, 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
전체 상태 0.262s 계산
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int a[20],b[20],N,test=0;
double d[70000];
double dist(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double DP(){
int s,i,j;
for(s=1;s<(1<<N);s++){
for(i=N-1;i>=0;i--) if(s&(1<<i)) break;
for(j=0;j<i;j++) if(s&(1<<j)){
d[s]=min(d[s],dist(a[i],b[i],a[j],b[j])+d[s^(1<<i)^(1<<j)]);
}
}
}
int main(){
freopen("in.txt","r",stdin);
while(scanf("%d",&N),N){
int i;
char s[25];
N*=2;
for(i=0;i<N;i++) scanf("%s%d%d",s,&a[i],&b[i]);
d[0]=0;
for(i=1;i<=(1<<N)-1;i++) d[i]=INF;
DP();
printf("Case %d: %.2lf
",++test,d[(1<<N)-1]);
}
return 0;
}
기억 검색 0.032s
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int a[20],b[20],N,test=0;
double d[70000];
double dist(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double DP(int s){
if(d[s]!=-1) return d[s];
double &ans=d[s];
ans=INF;
int i,j;
for(i=N-1;i>=0;i--) if(s&(1<<i)) break;
for(j=0;j<i;j++) if(s&(1<<j)){
ans=min(ans,dist(a[i],b[i],a[j],b[j])+DP(s^(1<<i)^(1<<j)));
}
return ans;
}
int main(){
freopen("in.txt","r",stdin);
while(scanf("%d",&N),N){
int i;
char s[25];
N*=2;
for(i=0;i<N;i++) scanf("%s%d%d",s,&a[i],&b[i]);
d[0]=0;
for(i=1;i<=(1<<N)-1;i++) d[i]=-1;
DP((1<<N)-1);
printf("Case %d: %.2lf
",++test,d[(1<<N)-1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.