问题1418--围栏翻新

1418: 围栏翻新

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

题目描述

小明的破旧围栏又要喷涂油漆了。围栏由N个木板构成,每个宽度都为1cm,但是高度各不相同。他给自己买了一个喷漆机器,喷涂头恰好也是1cm宽。
小明的喷漆机器是直接喷射的,因此喷头的每一个部位必须一直接触到木板,否则尤其会污染他的农田。并且机器也必须时刻与地面平行。可以看出,小明每次必须在同一高度对木板喷涂,可以从左到右直到没有围栏可以喷漆。这样,若干次喷漆之后,就可以将围栏翻新啦!
由于机器的特殊性,小明希望喷涂的次数尽量的少。如下图的围栏情况,共有5块木板,高度分别为2,3,4,1,2。第一次可以刷1~5,第二次刷1~3,第三次刷2~3,第四次刷3~3,第五次刷5~5。5次就可以刷完!(刷的顺序可以随意调整,也可以从上面开始刷)

小明想要知道至少需要刷多少次就可以把围栏都刷完,请你帮忙计算一下!

输入

第一行一个整数N,表示木板数量。
接下来N行,每行一个整数,表示每块木板依次的高度。

输出

翻新围栏所需的最少喷漆次数。

样例输入 Copy

5
2 3 4 1 2

样例输出 Copy

5

提示

【数据范围】
30%的数据1<=n<=10
70%的数据1<=n<=1000
100%的数据1<=n<=100000,对于每个木板的高度0<=hi<=10000。

来源/分类