问题 1339. -- brickbreaker

1339: brickbreaker

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

题目描述

贫穷的出题人靠搬砖维持生活。由于天气很热,出题人把砖头摆成了一堵宽度为n高度不一的砖墙来挡太阳。然而路过的城管认定这堵墙属于违规建筑,命令出题人立马拆除。由于出题人是搬砖老手,每次可以选择一段连续且均有砖头存在的区间[L,R],然后将第 L 块到第 R 块之间(含第 L 块和第 R 块)的砖墙高度减一。但是出题人已经搬了一天砖很累了,于时求助你如何花最少的次数把砖墙拆完

输入

输入包含两行,第一行包含一个整数 n,表示砖墙的宽度。 第二行包含 n 个整数,第i个整数为hi。 对所有数据,保证1 ≤ n ≤ 1000000,0 ≤ hi ≤ 100000

输出

仅一行,即拆墙所需的最少操作数。

样例输入

5
2 3 4 1 2

样例输出

5

提示

来源

[提交][状态][讨论版]