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

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

思路：递推

我们注意到，题目中说减速每次只能减

1

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

CPP

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

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

上代码：

CPP

#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;
}

没错，就是这么简单。

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

文章操作

思路：递推

上代码：

相关推荐

评论

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