京都大学プログラミングコンテスト2013

D - カーペット


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 128MB

総合研究7号館の引越しに伴い,研究室にカーペットを敷くことになった. この問題では研究室を上から見たときの床を,二次元平面上の多角形とみなす. 床の形状を表す要素数Nの数列\{a_i\}が与えられる. R_iを,左下の座標が(i,0)で右上の座標が(i+1,a_i)である各辺がx軸またはy軸に平行な長方形の境界及び内部領域とする. このとき,床を表す多角形はR_1 ∪ R_2 ∪ R_3 ∪ … ∪ R_Nによって表される. カーペットは長方形であればどんな大きさのものを何枚でも用意することができる. 以下の条件を満たすようにカーペットを配置し,研究室の床を全て覆いつくしたい.

研究室の床を覆い尽くすために必要なカーペットの最小数を求めよ.

入力例1の床

図D-1. 入力例1の床

入力例2の床

図D-2. 入力例2の床

入力形式

入力は以下の形式で与えられる.

N
a_1a_N

出力形式

研究室の床を覆い尽くすために必要なカーペットの最小数を1行に出力せよ.

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq a_i \leq 10^9
  • 入力値はすべて整数である.

入出力例

入力例1

3
1 2 1

出力例1

2

入力例2

10
1 2 2 1 3 4 3 1 2 2

出力例2

5

Source name

京都大学プログラミングコンテスト2013

Submit提出する