You have been given the job of forming the quiz teams for the next MCA CPCI Quiz Championship There are*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 members house as near as possible Let x be the distance between the houses of group x be the distance between the houses of group and so on You have to make sure the summation (x + x + x + … + xn) is minimized
Input
There will be many cases in the input file Each case starts with an integer N (N ≤ ) The next *Nlines will given the information of the students Each line starts with the students name followed by thex coordinate and then the y coordinate Both x y are integers in the range to Students name will consist of lowercase letters only and the length will be at most
Input is terminated by a case where N is equal to
Output
For each case output the case number followed by the summation of the distances rounded to decimal places Follow the sample for exact format
題意給定n有*n個人分成兩人一組的n組每個人在一個坐標上要求出所有組的兩人距離的和最小
思路明顯的集合最優配對問題i最為前i個人s作為前i個人能組成的所有集合j為前i個人中的一個人
這樣狀態轉移方程為dp[i][s] =min(dp[i][s] dis(i j) + dp[i ][s {i} {j}]集合用二進制來表示所以方程變為
dp[i][s] =min(dp[i][s] dis(i j) + dp[i ][s ^ <<i ^ <<j]但是這樣做時間不是很理想然後看了個詳細解法
裡面講得挺詳細的可以轉化為維
代碼
#include <stdioh>
#include <stringh>
#include <limitsh>
#include <mathh>
int n i j s;
double dp[<<];
struct Student{
char name[];
int x y;
} stu[];
double min(double a double b) {
return a < b ? a : b;
}
double dis(Student a Student b) {
return sqrt((double)((ax bx) * (ax bx) + (ay by) * (ay by)));
}
double dpp(int p) {
if (dp[p] != )
return dp[p];
dp[p] = INT_MAX;
int i j;
for (i = n ; i >= ; i )
if (p & ( << i))
break;
for (j = i ; j >= ; j )
if (p & ( << j))
dp[p] = min(dp[p] dis(stu[i] stu[j]) + dpp(p ^ (<<i) ^ (<<j)));
return dp[p];
}
int main(){
int t = ;
while (~scanf(%d &n) && n) {
n *= ;
s = <<n;
for (i = ; i < s; i ++)
dp[i] = ;
dp[] = ;
for (i = ; i < n; i ++)
scanf(%s%d%d stu[i]name &stu[i]x &stu[i]y);
printf(Case %d: %lfn t ++ dpp(s ));
}
return ;
}
From:http://tw.wingwit.com/Article/program/Web/201404/30639.html
