P1442 铁球落地

    • 115通过
    • 663提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 线段树 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    N(n≤100000)个平台上空有一个铁球,球每次落到某个平台上后,游戏者可以选择向左或向右滚,球滚动和落下的速度都是1。由于铁球的质量不太好,每次落下的高度不能超过MAX。设计一种策略,使得球尽快落到地面而不被摔碎。假设地面高度为0,且无限宽。

    输入输出格式

    输入格式:

    第一行是两个数n,max。

    第二行两个数,分别表示铁球起始位置的横纵坐标。

    接下来n行,第i行是三个正整数hi,li,ri,

    输入数据保证有解,且平台的高度互不相同、各边缘与横坐标的值均互不相同。

    输出格式:

    仅一个数,为铁球到达地面的最短时间。

    输入输出样例

    输入样例#1: 复制
    5 3
    6 10
    5 2 4
    9 3 9
    6 7 10
    2 1 5
    3 8 11
    
    输出样例#1: 复制
    15
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。