做题感悟:这题刚接触最优配对问题的第一题,开始因为数组开小了wa了一次。
解题思路:请点击~>
代码(二维):
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; const double PI = 3.1415926 ; const double INF = 99999999 ; const int MX =25 ; int n ; double dp[MX][1<<20] ; // 开数组要注意 struct node { double x,y ; }T[MX] ; double dis(node a,node b)// 计算两点距离 { return sqrt(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0)) ; } double min(double x,double y) // 比较大小 { return x < y ? x : y ; } void DP() { for(int i=0 ;i<n ;i++) for(int s=0 ;s<(1<<(i+1)) ;s++) { s ? dp[i][s]=INF : dp[i][s]=0 ; if(s&(1<<i)) { for(int j=i-1 ;j>=0 ;j--) if(s&(1<<j)) dp[i][s]=min(dp[i][s],dis(T[i],T[j])+dp[i-1][s^(1<<i)^(1<<j)]) ; } else if(i) dp[i][s]=dp[i-1][s] ; // i-1 的最优解复制下来 } } int main() { char s[MX] ; int q=1 ; while(~scanf("%d",&n)&&n) { n=n*2 ; for(int i=0 ;i<n ;i++) scanf("%s%lf%lf",s,&T[i].x,&T[i].y) ; DP() ; printf("Case %d: %.2lf\n",q++,dp[n-1][(1<<n)-1]) ; } return 0 ; }
代码(一维):
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; const double PI = 3.1415926 ; const double INF = 99999999 ; const int MX =25 ; double dp[1<<MX] ; int n,S ; struct node { double x,y ; }T[MX] ; double dis(node a,node b) { return sqrt(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0)) ; } double min(double x,double y) { return x > y ? y : x ; } void DP() { for(int s=1 ;s<S ;s++) { dp[s]=INF ; for(int i=n-1 ;i>=0 ;i--) if(s&(1<<i)) { for(int j=i-1 ;j>=0 ;j--) if(s&(1<<j)) dp[s]=min(dp[s],dis(T[i],T[j])+dp[s^(1<<i)^(1<<j)]) ; } } } int main() { char s[MX] ; int q=1 ; while(~scanf("%d",&n)&&n) { n=n*2 ; S=1<<n ; for(int i=0 ;i<n ;i++) scanf("%s%lf%lf",s,&T[i].x,&T[i].y) ; DP() ; printf("Case %d: %.2lf\n",q++,dp[S-1]) ; } return 0 ; }