铺设道路——贪心

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

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

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

Input
6   
4 3 2 5 3 5 

Output
9

解析：
f[i]表示当前 i 个坑所铺设的最少天数；
比较 a[i] 和 a[i-1]，
当 a[i] ≤ a[i-1] 时，在填 i-1的坑时，就能够顺便把 i 的坑填上；
当 a[i] > a[i-1] 时，在填 i-1的坑时，顺便把 i的 a[i-1]个坑填上，剩下的坑需要 i 单独填。
可以这样理解，小的坑肯定会被大的坑“带着”填掉。大的坑也会减少a[i]-a[i-1]的深度，可以说是“免费的”。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n;
int a[N],f[N];
void solve()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) 
    {
        if (a[i]<=a[i-1]) f[i]=f[i-1];
        else f[i]=f[i-1]+(a[i]-a[i-1]);
    }
    cout<<f[n];
}
signed main()
{
    ios;
    int T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}