题目描述

在历经多通向神殿正门的台阶总共有 n 级。小 G 的步长为 m , 即若小G当前处在台阶 i , 则他一步能够到达的位置区间为[max{i−m,1},min{i+m,n}] , 并且每跨出一步需要消耗 1 点体力。为了方便神的信徒朝拜 , 神在台阶上放置了若干个传送门 , 传送门指向指定的台阶。但由于神死去太久 , 传送门需要用 1 颗能量石来激活 , 穿过传送门不需要消耗体力。现在小 G 站在第一级台阶下 , 手上有 k 颗能量石。小 G 希望能够节省体力来应对神殿中的怪物 , 请你帮他计算一下 , 小 G 至少花费多少体力 , 才能达到神殿。到达第 n 级台阶就算到达神殿。重艰险后 , 小 G 终于来到了被怪物占领的神殿。

输入

第 1 行 2 个数字 , 分别代表 n , m , k。

第 2 行 n 个数字 t 1 ⋯t n , 分别代表第 1⋯n 级台阶上的传送门情况。若 t i =0 , 则该级台阶上没有传送门 , 若 t i

!=0 , 则该级台阶上存在一个通向第 t i 级台阶的传送门。

输出

一个数字 , 代表小 G 花费体力的最小值。 样例输入 复制 5 5 1 1 2 3 4 5 样例输出 复制 1 提示 数据范围与约定 对于 30%的数据 : 2⩽n⩽5×10 3 ,1⩽m⩽20,k⩽20

对于 75% 的数据 : 2⩽n⩽5×10 4 ,1⩽m⩽20,k⩽20

对于 100% 的数据 : 2⩽n⩽5×10 5 ,1⩽m⩽20,k⩽20

#include<bits/stdc++.h>
#define N 500100
#define M 30
using namespace std;
int n,m,k,i,j,x,nx,ans=INT_MAX,st,per;
int q[N*M][3],nex[N],f[N][M];
int main(){
    memset(f,127,sizeof(f));
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)scanf("%d",&nex[i]),nex[i]=nex[i]==i?0:nex[i];
    q[1][0]=1,q[1][1]=0,q[1][2]=k;
    for(i=j=1;i<=j;i++){
        x=q[i][0],st=q[i][1],per=q[i][2];//power
        if(x==n){
            ans=min(ans,st);
            continue;
        }
        if(nex[x]&&per&&st<=f[nex[x]][per-1])f[nex[x]][per-1]=st,q[++j][0]=nex[x],q[j][1]=st,q[j][2]=per-1;
        for(k=1;k<=m;k++){
            nx=x+k;
            if(nx>n||f[nx][per]<=st+1)continue;
            f[nx][per]=st+1;
            q[++j][0]=nx,q[j][1]=st+1,q[j][2]=per;
        }
    }
    printf("%d",ans);
    return 0;
}