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

Starlight237 · 2019-11-10 10:06:43 · 题解

T1

本题的数据是保证没有负环的（似乎根本无负权边），故只需考虑从i跳到\min\{n,i+k\}的情况。

枚举跳跃点，用前缀和的方式求出对应的路径长度（因为整个图就是一条链），求最小值即可。

code:

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define IOSIZE 20000000
static char in[IOSIZE],*p=in,out[20],*q=out,ch[20],*t=ch;
inline long long read(){
    reg long long x=0;reg char f=0;
    while(*p<48)f|=*p++=='-';
    while(*p>47)x=(x<<1)+(x<<3)+(*p++^48);
    return f?-x:x;
}
inline void write(long long x){
    x<0&&(*q++='-',x=-x);
    !x&&(*q++='0');
    while(x)*t++=x%10+48,x/=10;
    while(t!=ch)*q++=*--t;
}
int n,k;
static long long s[1000001];
int main(){
    fread(in,1,IOSIZE,stdin);
    n=read(),k=read();
    for(reg int i=1;i<n;++i)s[i]=s[i-1]+read();
    long long mi=0x3f3f3f3f3f3f3f3f;
    for(reg int i=1;i<=n-k;++i)mi=min(mi,s[n-1]-s[min(n,i+k-1)]+s[i-1]);
    write(mi);
    fwrite(out,1,q-out,stdout);
    return 0;
}