TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1970
  • Problem
  • P1970【2013新年赛】飞天忍者
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    忍者在高低错落的房屋顶上穿行,要从街的一端跳到另一端。
      这条街一共有N+1间房,标号由0到N,其中0为起点N为终点,每间房屋的高度为Hi,i、j两间房屋的水平距离为j-i。
      跳跃时只能从左向右跳,若要从i处跳到j处时,要求其水平距离不能超过i的高度,并且其间不能出现高度同时大于等于Hi和Hj的房屋。如果Hi>Hj,不消耗体力,否则花费Hj-Hi的体力值。
      问最少需要消耗多少体力才能到达终点?
    1<=N<=105, 1<=Hi<=109

    Input Format

    第一行一个整数N,第二行N+1个整数,第i个数对应为Hi。

    Output Format

    计算出到达终点所需的最小体力消耗。

    Sample Input

    7
    6 8 6 2 9 3 1 5

    Sample Output

    3