问题 4072 --积木大赛-NOIP2013D2T1

4072: 积木大赛-NOIP2013D2T1

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 24
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][832kb]

题目描述

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦,大厦可以看成由 n 块宽度为1的积木组成,第

输入

输入包含两行,第一行包含一个整数 n,表示大厦的宽度。

第二行包含 n 个整数,第i个整数为hi。

输出

仅一行,即建造所需的最少操作数。


其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5]

对于 30%的数据,有1 ≤ n ≤ 10;
对于 70%的数据,有1 ≤ n ≤ 1000;
对于 100%的数据,有1 ≤ n ≤ 100000,0 ≤ hi ≤ 10000。


样例输入

5
2 3 4 1 2

样例输出

5

提示

来源

[提交][状态]