题解：P12662 [KOI 2023 Round 2] 滑冰练习

luoguzbh0011 · 2025-06-01 08:07:03 · 题解

这么简单的题居然没有题解？

思路：递推

我们注意到，题目中说减速每次只能减 1，而加速可以随意加。那么这道题的关键就在于减速。
不难想到，如果我们用最快速度通过每个中间点可能就会来不及减速。
所以，我们就要用能顺利通过下一个中间点（或终点）的速度加 1 的速度通过这个中间点（当然，不能超过这个中间点的限速）
由于关系到下一个中间点，我们可以倒着递推。
这样我们就得到了递推式：

f[i]=min(f[i+1]+1,f[i]);

有了递推式，这题就好做啦。

上代码：

#include<bits/stdc++.h>
using namespace std;
long long f[500009];
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>f[i];
    long long ans=0;
    for(int i=n;i>=1;i--){
        f[i]=min(f[i+1]+1,f[i]);
        ans+=f[i];
    }
    cout<<ans;
}

没错，就是这么简单。