Burnling's Blog
0%

CF1987C Basil's Garden

发表于 更新于 分类于 ，

题意简述

有 $N$ 朵花，第 $i$ 朵花的高度为 $h_i$。

起风了。每秒钟从左至右，如果一朵花高于右侧的花或者是最后一朵花，那么这朵花的高度降低 $1$。

花的高度降至 $0$ 后不再降低。

求最少需要多少秒使 $N$ 朵花的高度全部为 $0$？

思路分析

一朵花的高度只会在右侧相邻花高度归零后才会归零。这一点是显然的。

第 $i$ 朵花的高度在这一步可以归零，当且仅当目前 $hi = 1$ 且 $h_i \gt h{i+1}$，也就是 $h_{i+1}=0$ 时。

那么就可以知道，这 $N$ 朵花的高度一定是从右至左依次归零的。

第 $i$ 朵花高度的归零时间严格晚于第 $i+1$ 朵花高度归零的时间。

令 $f_i$ 表示第 $i$ 朵花的归零时间。

我们分类讨论一下。

如果 $hi = h{i+1}$ ，那么第 $i$ 朵花需要等第 $i+1$ 朵花降低 $1$ 后才能重复第 $i+1$ 朵花的操作。也就是说，比右侧花多等了一秒。所以这种情况下，$fi = f{i+1} + 1$。

如果 $hi \lt h{i+1}$ ，那么第 $i$ 朵花需要等第 $i+1$ 朵花降低至 $hi$ 后才能重复第 $i+1$ 朵花的操作。也就是说，第 $i$ 朵花需要多等 $h_i=h{i+1}$ 的那一秒。所以这种情况下， $fi = f{i+1} + 1$。

如果 $hi \ge h{i+1}$，那么第 $i$ 朵花会与第 $i+1$ 朵花同步降低。如果一切顺利，那么这朵花会直接降至 $0$，此时花费 $hi$ 秒；如果降低过程中追上了右侧花的高度，那么就需要多等 $h_i=h{i+1}$ 的那一秒，此时花费 $f_{i+1} + 1$ 秒。

综上，$fi=\max(f{i+1}+1,h_i)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5+10;
long long A[maxN];
long long dp[maxN];

inline void solve(){
    int N;
    scanf("%d",&N);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i]);

    dp[N] = A[N];

    for(int i = N-1;i>=1;i--) dp[i] = max(dp[i+1] + 1,A[i]);

    printf("%lld\n",dp[1]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}