道路建设

【题目简述】

给定一个长度为 $n$ 的序列 $\{d_i\}$，每次可以选择一段所有数均大于 $0$ 的连续区间，并将这一段全部减一。要求把整个序列清零所需的最少操作次数。

【第一档部分分】

此时 $1\leq n\leq 10$。

显然 $n$ 极小，可以考虑枚举操作。每次枚举一个区间 $[l,r]$，若区间内所有位置均大于 $0$，就把它整体减一，然后继续搜索。

由于状态规模很小，这样可以通过第一档部分分。时间复杂度可以粗略看作 $\mathcal{O}(n^2\times n!)$。

【第二档部分分】

此时序列满足单峰性质。

对于单峰数列，可以以峰为中心考虑。每次选择当前还能被覆盖的最大区间进行一次操作，相当于从外向内一层一层填平。可以发现此时答案就是最深的 $d_i$。

这个部分分可以启发我们：一次操作不应该只盯着某个位置，而应该在处理较深位置的时候，顺带处理旁边较浅的位置。

【正解】

考虑一般情况。一个自然的贪心思路是，画出序列的高度图形可以发现，在填一个较深的位置时，必然应该顺带填掉相邻的较浅位置。

例如序列：

在处理第 $3$ 个数时，会顺带把它附近不高于它的一段一起填掉，剩下的贡献可以看作新的高度差。于是每当 $d_{i+1}>d_i$ 时，才会产生新的操作层数。

因此答案为：

也就是说，从左到右扫描序列，初始答案为 $d_1$，之后每次只在高度上升时把上升量加入答案即可。

手模可以看出正确性：已有的操作层可以延续到右侧不更高的位置；只有右侧比左侧更高时，才必须额外开出新的操作层。

【复杂度】

时间复杂度为 $\mathcal{O}(n)$，空间复杂度为 $\mathcal{O}(1)$。

【参考代码】

1#include <cstdio>2#include <algorithm>3using namespace std;4int n,Last,Now;5long long Ans=0;6int main(){7    scanf("%d",&n);8    for(int i=1;i<=n;i++){9        scanf("%d",&Now);10        Ans+=max(Now-Last,0);11        Last=Now;12    }13    printf("%lld\n",Ans);14    return 0;15}