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