P3572 [POI2014]PTA-Little Bird

    • 72通过
    • 255提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 单调队列 POI 2014 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    In the Byteotian Line Forest there are $n$ trees in a row.

    On top of the first one, there is a little bird who would like to fly over to the top of the last tree.

    Being in fact very little, the bird might lack the strength to fly there without any stop.

    If the bird is sitting on top of the tree no. i, then in a single flight leg it can fly toany of the trees no. $i+1,i+2,\cdots,i+k$ , and then has to rest afterward.

    Moreover, flying up is far harder to flying down. A flight leg is tiresome if it ends in a tree at leastas high as the one where is started. Otherwise the flight leg is not tiresome.

    The goal is to select the trees on which the little bird will land so that the overall flight is leasttiresome, i.e., it has the minimum number of tiresome legs.

    We note that birds are social creatures, and our bird has a few bird-friends who would also like to getfrom the first tree to the last one. The stamina of all the birds varies,so the bird's friends may have different values of the parameter $k$ .

    Help all the birds, little and big!

    从1开始,跳到比当前矮的不消耗体力,否则消耗一点体力,每次询问有一个步伐限制,求每次最少耗费多少体力

    输入输出格式

    输入格式:

    There is a single integer $n$ ($2\le n\le 1\ 000\ 000$ ) in the first line of the standard input:

    the number of trees in the Byteotian Line Forest.

    The second line of input holds $n$ integers $d_1,d_2,\cdots,d_n$ ($1\le d_i\le 10^9$ )separated by single spaces: $d_i$ is the height of the i-th tree.

    The third line of the input holds a single integer $q$ ($1\le q\le 25$ ): the number of birds whoseflights need to be planned.

    The following $q$ lines describe these birds: in the $i$ -th of these lines, there is an integer $k_i$ ($1\le k_i\le n-1$ ) specifying the $i$ -th bird's stamina. In other words, the maximum number of trees that the $i$ -th bird can pass before it has to rest is $k_i-1$ .

    输出格式:

    Your program should print exactly $q$ lines to the standard output.

    In the $i$ -th line, it should specify the minimum number of tiresome flight legs of the $i$ -th bird.

    输入输出样例

    输入样例#1: 复制
    9
    4 6 3 6 3 7 2 6 5
    2
    2
    5
    
    输出样例#1: 复制
    2
    1
    

    说明

    从1开始,跳到比当前矮的不消耗体力,否则消耗一点体力,每次询问有一个步伐限制,求每次最少耗费多少体力

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