主题链接~~>

做题情绪：时候最后有点蛋疼了，处理点的坐标处理晕了。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 ;

}