洛谷题库传送门

牛客题库传送门

题目描述

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

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n块首尾相连的区域，一开始，第i块区域下陷的深度为di。

春春每天可以选择一段连续区间[L,R]，填充这段区间中的每块区域，让其下陷深度减少1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为0。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为0。

输入描述

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

输出描述

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

示例1

输入

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 。

题解

首先来分析示例数据

这是按照示例数据画出来的示意图，
那么填过之后就变成了这样
这样太麻烦了，仔细观察图2，有没有发现一个规律，

其实我们可以这样子：
先把第1列的道路先填起来，记到天数sum中，然后将第一列下陷的深度后面的深度相比较，若后面的有一个小于它，则整条道路上都被填满了最浅的那个坑的深度的土，如图。

然后我们通过使用for循环遍历整条道路，在前一步的基础上，增加天数sum，如图

图片颜色标记错了，第5列的5也是红色

继续

图片颜色标记错了，第5列的5也是红色

最后

我们的算法应该这样实现

]

至此这道题就算完成了！

最后贴上完整代码

#include<bits/stdc++.h>
using namespace std;
int main(112)    //FangZuoBi
{
    //freopen ("road.in","r",stdin);
    //freopen ("road.out","w",stdout);
    int n,sum=0,l=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        {
            int a;
            scanf("%d",&a);
            if(a>l)
                sum+=(a-l);
            l=a;
        }
        printf("%d\n",sum);
    return 0;
}