首页 > 代码库 > 洛谷P2625 豪华游轮
洛谷P2625 豪华游轮
题目描述
有一条豪华游轮（其实就是条小木船），这种船可以执行4种指令：
right X : 其中X是一个1到719的整数，这个命令使得船顺时针转动X度。
left X : 其中X是一个1到719的整数，这个命令使得船逆时针转动X度。 forward X : 其中X是一个整数（1到1000），使得船向正前方前进X的距离。
backward X : 其中X是一个整数（1到1000），使得船向正后方前进X的距离。
随意的写出了n个命令，找出一个种排列命令的方法，使得船最终到达的位置距离起点尽可能的远。
输入输出格式
输入格式：第一行一个整数n(1 <= n <= 50)，表示给出的命令数。
接下来n行，每行表示一个命令。
输出格式：一个浮点数，能够走的最远的距离，四舍五入到6位小数。
输入输出样例
输入样例#1：
3forward 100backward 100left 90
输出样例#1：
141.421356
贪心思想。命令可以随意排列，那么开场肯定是全军突击（误），把所有前进指令都用完（走一半拐弯再走，肯定不如全程直走好），然后转向，尽可能接近180°，再倒着走。
求最适合的转向角度，我选择偷懒暴搜。偷懒的结果就是50分，剩下50分T掉了。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=60; 9 const double pi=3.141592653;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 double an[mxn];17 double fw[mxn];18 double nx,ny;19 int acnt=0,rcnt=0;20 double dist(double x1,double y1,double x2,double y2){21 return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );22 }23 int n;24 double ans=0;25 double ttd=0;26 void dfs(int rk,double now){27 // printf("%d %.4f\n",rk,now);28 if(rk>acnt){29 double tnow=fabs(now);30 double tmpx=nx+ttd*sin(tnow*pi/180);31 double tmpy=ny+ttd*cos(tnow*pi/180);32 // printf("%d %.4f %.4f\n",rk,tmpx,tmpy);33 ans=max(ans,dist(tmpx,tmpy,0,0));34 return;35 }36 dfs(rk+1,now);37 // printf("%.5f\n",now+an[rk]);38 dfs(rk+1,now+an[rk]);39 return;40 }41 int main(){42 n=read();43 int i,j;44 char ch[20];double x;45 nx=ny=0;46 for(i=1;i<=n;i++){47 scanf("%s%lf",ch,&x);48 if(ch[0]==‘f‘){49 fw[++rcnt]=x;50 }51 if(ch[0]==‘b‘){52 fw[++rcnt]=-x;53 }54 if(ch[0]==‘l‘){55 an[++acnt]=-x;56 // printf("in:%d",acnt);57 if(an[acnt]<-360)an[acnt]+=360;58 }59 if(ch[0]==‘r‘){60 an[++acnt]=x;61 if(an[acnt]<360)an[acnt]-=360;62 }63 }64 ttd=0;65 for(i=1;i<=n;i++){66 if(fw[i]>0)67 ny+=fw[i];68 else ttd+=fw[i];69 }70 sort(an+1,an+acnt+1);71 dfs(0,0);72 //73 //74 /* printf(" %d\n",dgans);75 nx+=ttd*cos(dgans);76 ny+=ttd*sin(dgans);*/77 // printf("%.4f %.4f\n",nx,ny);78 printf("%.6f\n",ans);79 return 0;80 }
正解是DP。懒得写了，从rlt那里抄了代码233
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 using namespace std; 6 const double pi=3.1415926535; 7 int n,sf,sb,p,ang[55]; 8 double ans; 9 bool f[105][405];10 int main()11 {12 scanf("%d",&n);13 for(int i=1;i<=n;i++)14 {15 int x;16 char ch[11];17 scanf("%s%d",ch,&x);18 if(ch[0]==‘f‘)19 sf+=x;20 if(ch[0]==‘b‘)21 sb+=x;22 if(ch[0]==‘r‘)23 ang[++ang[0]]=x;24 if(ch[0]==‘l‘)25 ang[++ang[0]]=-x;26 }27 f[0][0]=1;28 for(int i=1;i<=ang[0];i++)29 for(int j=0;j<360;j++)30 if(f[i-1][j])31 f[i][j]=1,f[i][(j+ang[i]+720)%360]=1;32 p=180;33 for(int i=0;i<360;i++)34 if(f[ang[0]][i])35 p=min(p,abs(i-180));36 ans=sqrt(sf*sf+sb*sb+2*sb*sf*cos(p*pi/180));37 printf("%.6f\n",ans);38 return 0;39 }
洛谷P2625 豪华游轮
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。