P5019 NOIP2018提高组铺设道路

题目描述

春春是一名道路工程师，负责铺设一条长度为 n 的道路。

铺设道路的主要任务是消除地表凹陷。整条道路被划分为n个连续的部分，在最初的阶段, 第i部分的下沉深度为di.

春春每天可以选择一段连续区间[L,R]来决定如何处理这一段连续区间内的每一小块区域，并使它们的下陷深度降低1个单位。当挑选特定区间时，请确保该区间的每一个小块区域在被处理之前都有一定的凹陷深度。

春春期待你能协助他规划一个解决方案，在最快的时间内将全部路段的所有下陷部位的深度降至零。

文件内容由两个部分组成。
第一行为一个整数n。
第二行为n个以空格分隔的整数值。
第i个值为di。
输出格式

输出结果为单一整数, 完成任务所需的时间最少为多少天

6
4 3 2 5 3 5

输出 #1
9

解题思路：我采用分治法来解决这个问题。首先确定一个特定的区域范围（L到R），并计算该区域内所有元素中最小的那个数值。接着，在这个区域内将每一个元素减去该最小值，并累加所需的总天数；这样就形成了断层0的位置（即分界点）。在这里需要注意的是，在算法中"断层"通常指的是某个特定的位置或者状态；