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

Azazеl · 2019-11-10 08:30:25 · 题解

蒟蒻在比赛最后半个小时才开始做的···交的时候数组少开了个0于是92->76

题意

给了你n-1个数，在一个地方i能没有花费地直接走到i+k或i-k(即跳过中间k个数),求这个最小花费

题解

很明显，我们设所有路的长度之和为tot,这个可以在输入时顺便统计。
之后，根据题意跳过中间k个数，那么怎么跳呢，很明显的贪心就是跳过k条长度之和最长的路径
这个很好统计，我会线段树前缀和，挨个统计即可，复杂度为O(n-k+1)

代码

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll a[1000005],d[1000005];
int main() {
    ll n,k,tot=0;
    scanf("%lld %lld",&n,&k);
    for(int i=1;i<n;i++) 
    {
        scanf("%lld",&a[i]);
        tot+=a[i];  
        d[i]=d[i-1]+a[i];
    }
    if(k==0)
    {
        printf("%lld",tot);
        return 0;
    }
    ll maxn=-1;
    for(int i=1;i<=n-k+1;i++) maxn=max(maxn,d[i+k-1]-d[i-1]);
    //我是不会告诉你之前我写成d[i+k]-d[i]了
    printf("%lld",tot-maxn);
    return 0;
}