LP2625 豪华游轮

Author Avatar
空気浮遊 2018年05月17日
  • 在其它设备中阅读本文章
  • 数论
  • 可行性dp
  • 贪心
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

挺有意思的一题。

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 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material