首页 > 代码库 > cf D Bear and Floodlight

cf D Bear and Floodlight

2024-11-13 13:19:02   202人阅读

题意：有n个灯，每个灯有一个照亮的角度，现在从点（l，0）走到点（r，0），问这个人若一直被灯照着能最多走多远？

思路；状压dp，然后通过向量旋转求出点（dp[i[,0）与灯的坐标（p[j].x,p[j].y）形成的向量然后旋转角度p[j].a，得到旋转之后的在x坐标轴上的点，然后与dp[i|(1<<j)]比较更新，找出最大值，再与右端点比较。有个情况，在旋转向量时，可能不与坐标轴有交点，你就把dp[i|(1<<j)]=r;

技术分享
 1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const double pi=acos(-1.0); 7  8 int n; 9 double l,r;10 struct node11 {12     double x,y;13     double a;14 }p[30];15 double dp[(1<<20)+10];16 17 int main()18 {19      while(scanf("%d%lf%lf",&n,&l,&r)!=EOF)20      {21         for(int i=0; i<n; i++)22         {23             double aa;24             scanf("%lf%lf%lf",&p[i].x,&p[i].y,&aa);25             p[i].a=(double)(aa*1.0*pi/180);26         }27         for(int i=0; i<(1<<n); i++) dp[i]=l;28         double ans=l;29         for(int i=0; i<(1<<n); i++)30         {31             ans=max(ans,dp[i]);32             for(int j=0; j<n; j++)33             {34                if((i&(1<<j))==0)35                {36                 double xx=dp[i]-p[j].x;37                 double yy=-p[j].y;38                 double x1=xx*cos(p[j].a)-yy*sin(p[j].a);39                 double y1=xx*sin(p[j].a)+yy*cos(p[j].a);40                 double sx=p[j].x+yy*(x1*1.0/y1);41                 if(sx>r) sx=r;42                 if(y1>=0)43                 {44                     dp[i|(1<<j)]=r;45                     continue;46                 }47                 dp[i|(1<<j)]=max(dp[i|(1<<j)],sx);48                }49             }50         }51         printf("%.10lf\n",min(ans,r)-l);52      }53      return 0;54 }
View Code

 

cf D Bear and Floodlight


联系
我们