CodeForces 385 D.Bear and Floodlight 状压DP

枚举灯的所有可能状态（亮或者不亮）（1<<20）最多可能的情况有1048576种

dp【i】表示 i 状态时灯所能照射到的最远距离（i 的二进制中如果第j位为0，则表示第j个灯不亮，否则就是亮）

当i&（1<< j）时代表第i个状态灯j不亮，此时可由状态i转移到状态 i ^ ( 1 << j) 即dp[(i^(1<<j))]=max(dp[(i^(1<<j))],get(dp[i],j))

get是从dp【i】的位置开始第j个灯所能照亮的最长距离

求距离时用反三角函数比较快

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

double x[N],y[N],a[N],l,r;

double dp[(<<)+];

double get(double x0,int i)

{

     double te=atan((r-x[i])/y[i]);

     te=min(te,atan((x0-x[i])/y[i])+a[i]);

     return x[i]+y[i]*tan(te);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cout<<setiosflags(ios::fixed)<<setprecision();

    int n;

    cin>>n>>l>>r;

    r-=l;

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

    {

        cin>>x[i]>>y[i]>>a[i];

        x[i]-=l;

        a[i]=a[i]/*pi;

    }

    memset(dp,,sizeof dp);

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

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

            if((i&(<<j))==)

                dp[(i^(<<j))]=max(dp[(i^(<<j))],get(dp[i],j));

    cout<<dp[(<<n)-]<<endl;

    return ;

}

/********************

********************/

巴特西

CodeForces 385 D.Bear and Floodlight 状压DP

最新文章

热门文章