铺设道路--大样例及PDF题面下载

题目描述:

大样例及PDF题面密码：Fei2Xue@Lian$Tian!，链接在样例输出下面

 

春春是一名道路工程师， 负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。 整段道路可以看作是 n 块首尾相连的区
域，一开始， 第 i 块区域下陷的深度为 di 。
春春每天可以选择一段连续区间 [L, R] ， 填充这段区间中的每块区域， 让其下陷深
度减少 1。 在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0 。
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变
为 0 。

输入格式:

输入文件名为 road.in。
输入文件包含两行，第一行包含一个整数 n，表示道路的长度。
第二行包含 n 个整数， 相邻两数间用一个空格隔开， 第 i 个整数为 di 。

输出格式:

输出文件名为 road.out。
输出文件仅包含一个整数，即最少需要多少天才能完成任务。

样例输入:

6
4 3 2 5 3 5

样例输出:

9

下载附加文件

提示:

一种可行的最佳方案是，依次选择：
[1,6]、 [1,6]、 [1,2]、 [1,1]、 [4,6]、 [4,4]、 [4,4]、 [6,6]、 [6,6]。
【 数据规模与约定】
对于 30% 的数据， 1 ≤ n ≤ 10 ；
对于 70% 的数据， 1 ≤ n ≤ 1000 ；
对于 100% 的数据， 1 ≤ n ≤ 100000 ， 0 ≤ di ≤ 10000 。

时间限制: 1500ms
空间限制: 512MB

---

来源: NOIP2018提高T1