Codeforces 385 D Bear and Floodlight

题目链接~~>

做题感悟：比赛的时候最后有点蛋疼了，处理点的坐标处理晕了，so~比赛完清醒了一下就AC了。

解题思路：

                状态压缩DP ,只有 20 个点，如果安排灯的时候只有顺序不同的问题，完全可以用状态压缩去递推出来，只是处理点的坐标的时候很麻烦，理清思路就好了。

    状态方程： dp [ S | (1 << i ) ]  = max( dp[ S |( 1 << i ) ] , dp[ S ] + W )  , 在状态 S 的情况下再添加 i 点（S 中先前不含 i 点），这样一直更新就 ok 了。

代码（有点挫了）：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      const double INF = 99999999 ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const int MY = 100000 + 5 ;
     
    
   

    

     

    
    

     

      const int MX = (1<<20) + 5 ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      double st ,sd ,dp[MX] ,ans ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double x ,y ,z ;
     
    
   

    

     

    
    

     

      }Tx[100] ;
     
    
   

    

     

    
    

     

      double ct(double x ,int i)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double sx = Tx[i].x ,sy = Tx[i].y ;
     
    
   

    

     

    
    

     
 double sa = Tx[i].z ; // 角度
     
    
   

    

     

    
    

     
 double dis = sqrt((sx-x)*(sx-x)+sy*sy) ;
     
    
   

    

     

    
    

     
 double a = sa*PI/(180*1.0) ,b ,L ,L1 ,c ;
     
    
   

    

     

    
    

     
 if(sx == x)   // 如果在正上方
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(a == PI/2.0)   return  ans ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 return sy * tan(a) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(x < sx)  // 在右边
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 double ex = acos(sy/dis) ;
     
    
   

    

     

    
    

     
 if(ex == a)  // 正好
     
    
   

    

     

    
    

     
 return L = dis*sin(a) ;
     
    
   

    

     

    
    

     
 else if(a < ex) // 小于
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       b = asin(sy/dis) ; // 度数
     
    
   

    

     

    
    

     

       L = dis*cos(b) ;
     
    
   

    

     

    
    

     

       a = a + b ;
     
    
   

    

     

    
    

     

       L = L - sy/tan(a) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c = acos(sy/dis) ;
     
    
   

    

     

    
    

     

       L1 = dis*sin(c) ;
     
    
   

    

     

    
    

     

       c = a - c ;
     
    
   

    

     

    
    

     

       L = L1 + sy*tan(c) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return L ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(x > sx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c = acos(sy/dis) ;
     
    
   

    

     

    
    

     
 if(c + a > PI/2.0)
     
    
   

    

     

    
    

     
 return ans ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       a = a + c ;
     
    
   

    

     

    
    

     

       L = sy*tan(a) ;
     
    
   

    

     

    
    

     
 return L - dis*sin(c) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (1<<n) ; ++i) // 初始化赋值
     
    
   

    

     

    
    

     

       dp[i] = -1 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i) // 初始化单个
     
    
   

    

     

    
    

     

       dp[1<<i] = ct(st ,i) ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 if(!(S&(1<<i)) && dp[S] != -1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[S|(1<<i)] == -1)
     
    
   

    

     

    
    

     

       dp[S|(1<<i)] = dp[S] + ct(st+dp[S] ,i) ;
     
    
   

    

     

    
    

     
 else dp[S|(1<<i)] = max(dp[S|(1<<i)] ,dp[S] + ct(st+dp[S] ,i)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 double Max = 0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       Max = max(Max ,dp[i]) ;
     
    
   

    

     

    
    

     
 if(Max >= sd-st)
     
    
   

    

     

    
    

     
 cout<<fixed<<setprecision(12)<<ans<<endl ;
     
    
   

    

     

    
    

     
 else cout<<fixed<<setprecision(12)<<Max<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%d%lf%lf" ,&n ,&st ,&sd))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans = sd - st ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 cin>>Tx[i].x>>Tx[i].y>>Tx[i].z ;
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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