P2339 提交作业usaco

    • 213通过
    • 505提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 线性结构 USACO
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    usaco

    题目描述

    贝西在哞哞大学选修了 C 门课,她要把所有作业分别交给每门课的老师,然后去车站和同学们一起回家。每个老师在各自的办公室里,办公室要等他们下课后才开,第 i 门课的办公室将在 Ti 分钟后开放。

    所有的办公室都在一条笔直的走廊上,这条走廊长 H 个单位,一开始贝西在走廊的尽头一侧,位于坐标为 0 的地方。第 i 门课的办公室坐标位于坐标为 Xi 的地方,车站的坐标为 B。贝西可在走廊上自由行走,每分钟可以向右或者向左移动一个单位,也可以选择停着不移动。如果走到一间已经开门的办公室,贝西就可以把相应的作业交掉了,走进办公室交作业是不计时间的。请帮助贝西计算一下,从她开始交作业开始,直到到交完所有作业,再走到车站,最短需要多少时间时间。

    输入输出格式

    输入格式:

    输入格式

    • 第一行:三个整数 C, H 和 B, 1 ≤ C ≤ 1000 , 1 ≤ H ≤ 1000 , 0 ≤ B ≤ H

    • 第二行到 C + 1 行:第 i + 1 行有两个整数 Xi 和 Ti, 0 ≤ Xi ≤ H , 0 ≤ Ti ≤ 10000

    输出格式:

    输出格式

    • 单个整数,表示贝西交完作业后走到车站的最短时间

    输入输出样例

    输入样例#1: 复制
    4 10 3
    8 9
    4 21
    3 16
    8 12
    
    输出样例#1: 复制
    22

    说明

    走到坐标 8 处,第 9 分钟交一本作业,等到第 12 分钟时,交另一本作业。再走到坐标 4 处交作业,最后走到坐标 3 处,交最后一本作业,此地就是车站所在位置,共用时 22 分钟

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。