【题目来源】
洛谷：P5019 [NOIP 2018 提高组] 铺设道路 - 洛谷 (luogu.com.cn)
【题目描述】
春春是一名道路工程师，负责铺设一条长度为 \(n\) 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 \(n\) 块首尾相连的区域，一开始，第 \(i\) 块区域下陷的深度为 \(d_i\) 。
春春每天可以选择一段连续区间 \([L,R]\) ，填充这段区间中的每块区域，让其下陷深度减少 \(1\)。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 \(0\) 。
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 \(0\) 。
【输入】
输入文件包含两行，第一行包含一个整数 \(n\)，表示道路的长度。 第二行包含 \(n\) 个整数，相邻两数间用一个空格隔开，第 \(i\) 个整数为 \(d_i\) 。
【输出】
输出文件仅包含一个整数，即最少需要多少天才能完成任务。
【输入样例】
6
4 3 2 5 3 5
【输出样例】
9
【解题思路】
【算法标签】
《洛谷 P5019 铺设道路》 #贪心# #树状数组# #NOIP提高组# #2018#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, a[100005], f[100005]; // n: 数组长度, a: 输入数组, f: 动态规划数组int main()
{// 输入数组长度ncin >> n;// 输入数组元素for (int i = 1; i <= n; i++) {cin >> a[i];}// 初始化动态规划数组f[1] = a[1]; // 第一个元素的最小和就是它本身// 动态规划计算最小和for (int i = 2; i <= n; i++) {if (a[i - 1] >= a[i]) {// 如果前一个元素大于等于当前元素，直接继承前一个结果f[i] = f[i - 1];} else {// 否则需要增加差值部分f[i] = f[i - 1] + (a[i] - a[i - 1]);}}// 输出最终结果cout << f[n];return 0;
}
【运行结果】
6
4 3 2 5 3 5
9