UVA-10911 - Forming Quiz Teams(状态压缩)

题目链接~~>

做题感悟：这题一看就用状态压缩，没多想一些WA了，一看没有输出 case ，改后AC。

解题思路：不管是递推的状态压缩还是记忆化搜索的状态压缩，都是从整体中先拿出两个点，只不过递推是从小部分推到整体，而记忆化则是从整体推到个体。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MY = 20 + 10 ;
     
    
   

    

     

    
    

     

      const int MX = 400 + 10 ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      double dp[1<<17],d[18][18] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y ;
     
    
   

    

     

    
    

     

      }T[MY] ;
     
    
   

    

     

    
    

     

      double dis(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return sqrt(pow(T[x].x-T[y].x,2.0)+pow(T[x].y-T[y].y,2.0)) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++) // 这样预处理一下时间差距很大
     
    
   

    

     

    
    

     
 for(int j=i+1 ;j<n ;j++)
     
    
   

    

     

    
    

     

       d[i][j]=d[j][i]=dis(i,j) ;
     
    
   

    

     

    
    

     
 for(int S=0 ;S<(1<<n) ;S++)
     
    
   

    

     

    
    

     

       dp[S]=0 ;
     
    
   

    

     

    
    

     
 for(int S=0 ;S<(1<<n) ;S++)// 枚举每一种状态
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 if(S&(1<<i))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int j=0 ;j<n ;j++) // 把 i 和 j 分别摘出来
     
    
   

    

     

    
    

     
 if((S&(1<<j))==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[S|(1<<j)]!=0)
     
    
   

    

     

    
    

     

       dp[S|(1<<j)]=min(dp[S^(1<<i)]+d[i][j],dp[S|(1<<j)]) ;
     
    
   

    

     

    
    

     
 else dp[S|(1<<j)]=dp[S^(1<<i)]+d[i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 char s[MX] ;
     
    
   

    

     

    
    

     
 int cse=1 ;
     
    
   

    

     

    
    

     
 while(scanf("%d",&n),n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       n*=2 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%s%d%d",s,&T[i].x,&T[i].y) ;
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     
 printf("Case %d: %.2lf\n",cse++,dp[(1<<n)-1]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MY = 20 + 10 ;
     
    
   

    

     

    
    

     

      const int MX = 400 + 10 ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      char s[MY] ;
     
    
   

    

     

    
    

     

      double dp[1<<17],d[18][18] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y ;
     
    
   

    

     

    
    

     

      }T[MY] ;
     
    
   

    

     

    
    

     

      double dis(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return sqrt(pow(T[x].x-T[y].x,2.0)+pow(T[x].y-T[y].y,2.0)) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      double DP(int S) // 记忆化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(dp[S]!=-1)  return dp[S] ;
     
    
   

    

     

    
    

     
 double &ans =dp[S] ;
     
    
   

    

     

    
    

     

       ans = INF ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 if(S&(1<<i))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int j=0 ;j<n ;j++)
     
    
   

    

     

    
    

     
 if(S&(1<<j))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 double temp=DP(S^(1<<i)^(1<<j))+d[i][j] ;
     
    
   

    

     

    
    

     

       ans = min(ans,temp) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       n*=2 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%s%d%d",s,&T[i].x,&T[i].y) ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 for(int j=i+1 ;j<n ;j++)
     
    
   

    

     

    
    

     

       d[i][j]=d[j][i]=dis(i,j) ;
     
    
   

    

     

    
    

     
 for(int S=0 ;S<(1<<n) ;S++)
     
    
   

    

     

    
    

     

       dp[S]=-1 ;
     
    
   

    

     

    
    

     

       dp[0]=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int cse=1 ;
     
    
   

    

     

    
    

     
 while(scanf("%d",&n),n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

     
 double ans=DP((1<<n)-1) ;
     
    
   

    

     

    
    

     
 printf("Case %d: %.2lf\n",cse++,ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38275461