/ SYOI / 题库 /

涂墙

涂墙

题目描述

乐乐在涂漆一面墙,这个墙是由很多宽为 1 ,高为 \(h_i\) 的方块构成的,乐乐的刷子宽为 1 ,他只能水平涂,不能竖直涂,涂过的地方可以重复涂。现在他想知道,最少涂多少次可以将这面墙涂完?

输入格式

输入共2行,第一行输入一个正整数 \(n\)

接下来一行输入 \(n\) 个整数 \(h_i\),分别表格每个方块的高度,方块是按次序摆放的。

输出格式

输出最少涂几次

输入输出样例

输入#1

5 
2 2 1 2 1

输出#1

3

说明/提示

样例说明:

在最上面先水平涂一次,然后将第一块和第二块方块按水平再涂一次(没涂过的地方),最后将第四块方块按水平涂一次,最少涂 3 次。

数据范围与约定:

\(1\le n\le5\times10^4\),\(1\le h_i\le10^9\)

信息

ID
1001
难度
3
分类
分治 点击显示
标签
递交数
2
已通过
1
通过率
50%
上传者

相关

在下列训练计划中:

验题