题解 AT4284 【[ABC116C] Grand Garden】
< 完全一致
[P1969](https://www.luogu.com.cn/problem/P1969) 完全一致
[P5019](https://www.luogu.com.cn/problem/P5019) 完全一致
[AT4284(本题)](https://www.luogu.com.cn/problem/AT4284) 完全一致
[CF448C](https://www.luogu.com.cn/problem/CF448C) 极其相似
### 解法
核心要点：**贪，都可以贪**
贪心做法，从前往后遍历，每当找到一个 $h_{i} > h_{i - 1}$ 操作次数就加上 $h_{i} - h_{i - 1}$
### 为什么这样解
可以理解为当找到一个高点 （即 $h_{i} > h_{i - 1}$），那就可以顺便把他后面递减的区间一起干掉。由于区间保证递减 （即 $h_{i} \leq h_{i - 1}$），所以可以保证像金字塔那样，每次操作的区间都是连续的。
（黑色框表示每个点需求的高度，红色框表示操作顺序）
如果遇到操作区间内（即 $h_{i} > h_{i - 1}$），那么就会出现这种状况
（断档了）
### AC Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
long long n, a, last(0), ans(0);
cin >> n;
for (long long i = 1; i <= n; ++i)
{
cin >> a;
ans += a > last ? (a - last) : 0;
last = a;
}
cout << ans << endl;
return 0;
}
```
]]>