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

· · 题解

题目大意是说，你需要从一个无向图的点1到达点n，n就是最后一个点。这个图是一条直线排列，每个节点（点1，点n除外）都连接了两条边，如果该点编号为k，则两条边分别通向分别通向点k-1以及点k+1。

不过，你还有一个传送半径为s的传送机，它可以将你传送到（设你现在在点f）点f-k或者点f+k，注意，它只能使用一次。

首先，我们要确定的是，绝对不能往前面传送。因为使用后你必须从更远的地方再走到点n，因此，不能向前传送！

那么，这题该怎么办呢？事实上，只需要枚举使用传送器的点f就好了。看一看那个方案最快。这是一份代码:

注意，这里事实上不需要计算不使用传送器的情况。因为所有边权不会为负数，因此，跳过一些边总比不跳过任何边快一些。

#include<stdio.h>
unsigned long long a[10000001];//记录边的长度
int main()
{
    unsigned long long n,k;//点数以及传送半径
    scanf("%lld %lld",&n,&k);
    unsigned long long i;
    for(i=1;i<=n-1;++i)
        scanf("%lld",&a[i]);//读入
    unsigned long long now=1;
    unsigned long long ans=1000000000000000010;//取可能的最大值，也就是最大点数*最长边长，免得我们想象的最大值实际比答案还小。普通的long long 是无法存储的，需要无符号的long long 
    unsigned long long j;
    unsigned long long sum;
    for(i=1;i<=n-k;++i)//传送的点，即上文所说的点f
    {
        now=i+k;//向后传送后的点编号
        sum=0;
        for(j=1;j<=now-k-1;++j)//累加前面要走的，要从点1枚举到传送点f，由于边存的是从点u到点u+1的距离，只需循环到now-k-1
            sum+=a[j];
        for(j=now;j<n;++j)//累加后面要走的
            sum+=a[j];//统计在这个点传送的长度
        if(sum<ans)
            ans=sum;//如果比答案小就更新
    }
    printf("%lld",ans);//输出结果
    return 0;
}

但是，上面的代码会超时。为什么？因为它每次都要计算从点1到点f，从点now 到点n的距离。

那我们因该如何优化？其实，只需要使用两个数组存储距离。

设f[i]为从点1到点i的距离。设h[i]为从点n到点i的距离。

那么怎么推出f[i]和h[i]呢？递推公式如下

f[i]=f[i-1]+a[i-1] 也就是说，从点1到点i的距离就是从点i-1加上从点i-1到点i的边长，且f[0]=0

h[i]=h[i+1]+a[i] 指的是，从点n到点i的距离就是从点i+1加上从点i到点i+1的边长，且f[n]=0,注意，这里我们要逆着推

这样，点now的长度就是f[now-k] 从点1到传送点f + h[now] 从点n到现在的点

AC代码如下：

#include<stdio.h>
unsigned long long a[10000001];
unsigned long long f[10000001];
unsigned long long h[10000001];//意义见上文
int main()
{
    unsigned long long n,k;
    scanf("%lld %lld",&n,&k);
    unsigned long long i;
    for(i=1;i<=n-1;++i)
        scanf("%lld",&a[i]);//读入
    unsigned long long now=1;
    unsigned long long ans=1000000000000000010;
    unsigned long long j;
    unsigned long long sum;
    f[0]=0;
    h[n]=0;
    for(i=n-1;i>=1;--i)
    {
        h[i]=h[i+1]+a[i];//初始化h数组
    }
    for(i=1;i<=n;++i)
    {
        f[i]=f[i-1]+a[i-1];//初始化f数组
    }
    for(i=1;i<=n-k;++i)//由于过了点n-k就无法传送了，所以不用枚举
    {
        now=i+k;
        sum=0;
        sum+=f[i];
        sum+=h[now];
        if(sum<ans)
            ans=sum;
    }
    printf("%lld",ans);//输出答案
    return 0;
}