P12662 [KOI 2023 Round 2] 滑冰练习

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

你打算在给定的滑冰赛道上进行滑冰练习。该赛道由起点、$N$ 个中间点和终点组成。练习开始于起点，起始速度为 $0$，然后按照编号递增的顺序依次经过第 $1$ 个中间点到第 $N$ 个中间点，最后以速度 $0$ 到达终点后结束。 每个中间点都有一个速度限制 $V_i$。在前往下一个中间点的过程中，必须控制速度不超过该点的速度限制。你可以任意提升速度，但若要降低速度，每次只能从上一个经过的中间点的速度减少 $1$。此外，除起点和终点外，任何位置上的速度不能为 $0$。保持原有速度也是允许的。 本次练习的成果由各中间点的速度之和决定，因此你希望最大化这个总和。给定赛道的速度限制，计算你在该赛道中最多能取得的练习成果。 例如，在中间点数为 $3$，速度限制为 $V = [2, 3, 1]$ 的情况下，如果你在第 $2$ 个中间点以速度 $3$ 前进，就无法将速度调整为不超过第 $3$ 个中间点限制（即 $1$）的数值。因此，这样的安排不可行。 一种可行的安排是按顺序调整速度为 $[2, 2, 1]$，其速度之和为 $2 + 2 + 1 = 5$。其他可行的安排还包括 $[1, 1, 1]$ 和 $[1, 2, 1]$，但它们的速度之和也不会超过 $5$。因此，在此赛道中可以获得的最大练习成果为 $5$。

第一行输入一个整数 $N$。 第二行输入 $V_1, V_2, \dots, V_N$，各数之间以空格分隔。

输出一个整数，表示最大可获得的练习成果（即速度总和）。

**限制条件** - 所有给定的数都是整数。 - $1 \leq N \leq 500\,000$ - $1 \leq V_i \leq 1\,000\,000\,000 \quad (1 \leq i \leq N)$ **子任务** 1. （8 分）$N \leq 8,\ V_i \leq 8 \quad (1 \leq i \leq N)$ 2. （12 分）$N \leq 500,\ V_i \leq 500 \quad (1 \leq i \leq N)$ 3. （17 分）$N \leq 5\,000,\ V_i \leq 5\,000 \quad (1 \leq i \leq N)$ 4. （10 分）$N \leq 5\,000$ 5. （53 分）无附加限制 翻译由 ChatGPT-4o 完成