Codeforces 385D - Bear and Floodlight - JavaScript

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

385D - Bear and Floodlight

题目大意： 有一个人从( l , 0 ) 想走到 ( r , 0 )，有 n 盏路灯，位置为( xi , yi )，每盏路灯都有一个照射的角度ai

这个角度内的区间都被照亮，问你走之前任意调路灯的方向，这个人只能走路灯照亮的地方，问你他最多能往

r 方向走多少距离。

思路： 本来我想的是才20盏灯直接枚举灯的顺序也不会超时的吧，复杂度才20！* 20 (ps：我错了我是猪，20！复杂度很高)，

结果GG，T掉了，改成状态压缩就过了，状态压缩也跑了2000+ms。dp[ i ]，表示 i 这个状态下的到达的最长距离。

dp[ ( 1 << n ) - 1 ]就是我们要用的答案，将一个路灯照亮的距离往上加的时候，用正弦定理计算距离。

#include<bits/stdc++.h>

using namespace std;

const double pi=acos(-);

const int N=;

int n;

double l,r,dp[<<N];

struct lit

{

    double x,y,a;

}w[];

double dis(double x1,double y1,double x2,double y2)

{

    double a=(x1-x2)*(x1-x2);

    double b=(y1-y2)*(y1-y2);

    return sqrt(a+b);

}

double work(double pre,int g)

{

    double d=dis(pre,,w[g].x,w[g].y);

    double c=acos(fabs(w[g].x-pre)/d);

    if(w[g].x<pre) c=pi-c;

    c=pi-w[g].a-c;

    if(c<)

    {

        printf("%.12f\n",r);

        exit();

    }

    double len=d*sin(w[g].a)/sin(c);

    return min(r,pre+len);

}

int main()

{

    scanf("%d%lf%lf",&n,&l,&r);

    r-=l;

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

    {

        scanf("%lf%lf%lf",&w[i].x,&w[i].y,&w[i].a);

        w[i].x-=l;

        w[i].a=w[i].a/180.0*pi;

    }

    memset(dp,,sizeof(dp));

    int up=<<n;

    for(int i=;i<up;i++)

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

    {

        if((i&(<<j))==) dp[i^(<<j)]=max(dp[i^(<<j)],work(dp[i],j));

    }

    printf("%.12f\n",dp[up-]);

    return ;

}