← 返回题目列表

AtCoder · npcapc_2024_k

K. 与魔法和平相处

中文机器翻译题面 查看原题

配点 : 100 点

問題文

NPCA国家水平排列 由 N 方块组成,从左侧开始。 它的编号为 1 到 N 。在这里,群众 i 的高度 比方说 H_i 。一开始,H_1=H_2=\dots=H_N=0 。 关于

各 1\le i\le N-1 , H_i 和 H_{i+1} 之间的差的绝对值为 当小于 D_i 时,质量 i 和正方形 i+1 会引起你们之间的纠纷。现在,NPCA国家爱好和平的国王纳普卡的目标是确保任何相邻方格之间不发生冲突。因此,纳普卡使用了以下魔法。 您可以将其乘以超过 0 倍。 选择

  • H_i=H_{i+1}=\dots=H_{j} 的整数 i,j(1\le i\le j\le N) 添加 H_i,H_{i+1},\dots,H_{j} 至 不包括 1 。

找出 Napuka 必须施展魔法才能实现其目标的最少可能次数。

制約

  • 2 \le N \le 100
  • 0 \le D_i \le 1000

入力

输入是按以下格式从标准输入给出的。

N
D_1 D_2 \dots D_{N-1}

出力

输出答案。


入力例 1

4
2 3 1

出力例 1

4

开始,(H_1,H_2,H_3,H_4)=(0,0,0,0) 。例如,你可以像这样施展魔法:

  • (i,j)=(1,3) 。(H_1,H_2,H_3,H_4)=(1,1,1,0) 变为。 给定了
  • (i,j)=(1,2) 。(H_1,H_2,H_3,H_4)=(2,2,1,0) 变为。 给定了
  • (i,j)=(2,2) 。(H_1,H_2,H_3,H_4)=(2,3,1,0) 变为。 给定了
  • (i,j)=(2,2) 。(H_1,H_2,H_3,H_4)=(2,4,1,0) 变为。 给定了

魔法,直到你达到目标 4 次,这是最小值。 i=j 变为 请注意,您还可以选择 i,j 。 有


入力例 2

3
0 0

出力例 2

0

入力例 3

10
1 9 5 6 2 7 1 4 8

出力例 3

22