题解 P5638 【【CSGRound2】光骓者的荣耀】

love_luke · 2019-11-10 07:15:52 · 题解

因为题目保证了边权值大于等于0，而所有城市是一条链，易知只要一直往终点走就行了。而传送器的作用就是帮你跳过一段路，我们要做的就是求出这段跳过的路的最大权值。

用前缀和处理。注意要开long long。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long a[1000005];
int main()
{
    long long n,k,maxx=0;
    scanf("%ld%ld",&n,&k);
    for (int i=1;i<n;++i)
    {
        scanf("%ld",&a[i]);
        a[i]+=a[i-1];//前缀和
    }
    for (int i=1;i<=n-k;++i)
    {
        maxx=max(maxx,a[i+k-1]-a[i-1]);//求最多能越过的权值
    }
    printf("%ld",a[n-1]-maxx);//别忘了用总路程减去能越过的路程
    return 0;
}