LP2625 豪华游轮

Author Avatar
ajcxsu 2018年05月17日
  • 47 次阅读

挺有意思的一题。

Problem

有一条豪华游轮(其实就是条小木船),这种船可以执行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个命令,找出一个种排列命令的方法,使得船最终到达的位置距离起点尽可能的远。

Solution

按照贪心的思想。
若先走forward,然后转弯,然后再走forward
由三角形性质,不如不转弯连续走forward
所以由此forward指令肯定连在一起

而backward如果要走的尽量远,backward也同样要连在一起。

由此,backward和forward合并之后,你可以选择是否转弯(因为没用的转弯可以放在最末尾进行),进行一次可行性dp,看看能够得到什么角度。
先走forward,找到一个最优的角度旋转,走backward,计算即可。

这种方法也说明了为什么即使backward只能往回走,backward也必须要连在一起。因为如果部分backward在最优角度,而部分backward在差一些的角度,肯定不如全部的backward都放在最优的角度行走。

Code

// Code by ajcxsu
// Problem: money_boat

#include<bits/stdc++.h>
using namespace std;

int go,back;
int pack[100];

bool f[100][360];

int main() {
    int n,p=1;
    cin>>n;
    string cmd;
    int x;
    for(int i=1;i<=n;i++) {
        cin>>cmd>>x;
        if(cmd[0]=='f') go+=x;
        else if(cmd[0]=='b') back+=x;
        else if(cmd[0]=='l') pack[p++]=x;
        else pack[p++]=-x;
    }
    f[0][0]=1;
    for(int i=1;i<=p;i++)
    for(int j=0,fr;j<360;j++) {
        fr=(j-pack[i]+360)%360;
        f[i][j]|=f[i-1][j]|f[i-1][fr];
    }
    int dir=0x3f3f3f3f;
    for(int i=0;i<360;i++)
        if(f[p][i]) dir=min(dir, abs(i-180));
    dir=(720-dir)%360;
    double ra=1.0*dir/180.0*M_PI;
    double xx=back*sin(ra), yy=back*cos(ra)+go;
    printf("%.6lf\n", sqrt(xx*xx+yy*yy));

    return 0;
}

本文链接:https://acxblog.site/archives/sol-luogu-2625.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。