问题1003--涂漆

1003: 涂漆

时间限制: 1 Sec  内存限制: 128 MB
提交: 145  解决: 46
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY在涂漆一面墙,这个墙是由很多宽为1,高为hi的方块构成的,BSNY的刷子宽为1,他可以水平涂,也可以垂直涂,涂过的地方可以重复涂。现在他想知道,最少涂多少次可以将这面墙涂完。

输入

输入n,然后接下来一行输入n个整数hi

输出

输出最少涂几次

样例输入 Copy

5 
2 2 1 2 1

样例输出 Copy

3

提示

【样例说明】
可以先水平最下面涂一次,然后第一块和第二块水平再涂一次,最后第四块水平或垂直涂一次,最少涂3次
【数据规模和约定】
1<=n<=100000
1<=hi<=10^9

来源/分类