TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1970
  • 問題
  • P1970【2013新年赛】飞天忍者
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    忍者在高低错落的房屋顶上穿行,要从街的一端跳到另一端。
      这条街一共有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

    入力形式

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

    出力形式

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

    サンプル入力

    7
    6 8 6 2 9 3 1 5

    サンプル出力

    3