挺有意思的一题。

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://pst.iorinn.moe/archives/sol-luogu-2625.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆