[CF1523H]Hopping Around the Array

本文主要是介绍[CF1523H]Hopping Around the Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Hopping Around the Array

题解

**卡常题。

我们可以先将删除一个格子的操作看成用代价 $0$ 跳过一个格子，跳到 $x+a_{x}$ 视作代价为 $1$ 的跳跃。

由于 $k$ 值较小，我们可以先设计一个dp，令 $dp_{i,j,k}$ 表示从点 $i$ 出发进行 $j$ 次代价为 $1$ 的跳跃与 $k$ 次代价为 $0$ 的跳跃所能到达的最远的。
很明显，如果我们要往下一次跳跃转移的话我们肯定会先找到 $i,dp_{i,j,k}]$ 之间 $a_{x}+x$ 最大的点进行转移。
但它总的跳跃次数会特别大，时间复杂度 $O\left((n+q)n k^2\right)$ ，明显会T掉，空间也会爆掉，我们考虑如何优化。

我们可以通过倍增进行维护。
可以证明，它每次都会跳跃到 $a_{x}+x$ 最大的一个点。
因为在这一次跳跃中，没有点能比这个点在下一次跳得更远的点，而这个点可以使下一次的 $a_{x}+x$ 尽可能大，所以在相同的跳跃次数中，它一定可以使终点尽可能地远。
所以我们下一次转移只需要从 $a_{x}+x$ 最大的点转移过来即可，每个点的转移点都是固定的。
我们将原 $d p$ 的定义改成 $dp_{i,j,k}$ 表示从点 $i$ 出发，经过 $2^j$ 次代价为 $1$ 的跳跃， $k$ 次代价为 $0$ 的跳跃所能到达的最远的点。
转移方程式容易得到，记 $c a l c (l, r)$ 表示区间 $[l, r]$ 间 $a_{x}+x$ 最大的点的 $x$ ：
$dp_{i,j,k+\Delta}=\max_{l=0}^{k}(dp_{calc(i,dp_{i,j-1,l}),j-1,k-l})+\Delta$

而我们从一个起点开始到一个终点的最小步数可以像倍增求 $l c a$ 一样求，从这个起点开始倍增。
我们设 $A_{k}$ 表示在进行了 $x$ 次花费为 $1$ 的操作， $k$ 次花费为 $0$ 的操作后，我们能走到的最远点。
我们每要多走 $2^j$ 步时有转移式：
$A_{k}=\max_{i=0}^{k}(dp_{A_{i},j,k-i})$
我们像求 $l c a$ 一样，找到它最多走多少步不会超过终点，那之后再走一步就是走到终点的最小步数。

有了这种想法，我们很容易发现对于很多个的询问这种做法也是适用的，它单次询问的时间复杂度是较小的~~时间复杂度确实很小，但常数不小~~。
于是我们只需要先处理出 $d p$ 数组，再对单个询问倍增求出答案即可。
对于 $c a l c (l, r)$ 函数，我们可以通过st表进行维护。

时间复杂度 $O\left((n+q)k^2log\,n\right)$ 。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 40005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int zero=500;
const LL jzm=2333;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int n,q,a[MAXN],st[MAXN][20],f[MAXN][35][20],lg[MAXN],A[35],tmp[35],B[35];
int Max(const int x,const int y){return x+a[x]>y+a[y]?x:y;}
inline int query(int l,int r){if(l>r)return 0;r=min(r,n);const int k=lg[r-l+1];return Max(st[l][k],st[r-(1<<k)+1][k]);}
signed main(){read(n);read(q);lg[1]=0;for(reg int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(reg int i=1;i<=n;i++)read(a[i]);for(reg int i=1;i<=n;i++)st[i][0]=i;for(reg int i=1;i<=lg[n];i++)for(reg int j=1;j<=n-(1<<i)+1;j++)st[j][i]=Max(st[j][i-1],st[j+(1<<i-1)][i-1]);for(reg int i=1;i<=n;i++)for(reg int j=0;j<=30;j++)f[i][j][0]=i+a[i]+j;for(reg int l=0;l<lg[n];l++)for(reg int i=1;i<=n;i++)for(reg int j=0;j<=30;j++){for(reg int k=0;j+k<=30;k++)f[i][j+k][l+1]=max(f[i][j+k][l+1],f[query(i,f[i][j][l])][k][l]);for(reg int k=0;j+k<=30;k++)f[i][j+k][l+1]=max(f[i][j][l+1]+k,f[i][j+k][l+1]);}for(reg int i=1;i<=q;i++){int l,r,k,minn=2;read(l);read(r);read(k);if(l==r){puts("0");continue;}if(l+a[l]+k>=r){puts("1");continue;}for(reg int j=0;j<=k;j++)A[j]=l+a[l]+j;for(reg int j=lg[r-l+1];j>=0;j--){for(reg int i1=0;i1<=k;i1++)tmp[i1]=A[i1],B[i1]=query(l,A[i1]);bool flag=0;for(reg int i1=0;i1<=k&&!flag;i1++)for(reg int i2=0;i1+i2<=k;i2++)if(f[B[i1]][i2][j]>tmp[i1+i2]){tmp[i1+i2]=f[B[i1]][i2][j];if(tmp[i1+i2]>=r){flag=1;break;}}if(flag)continue;minn+=(1<<j);for(reg int i1=0;i1<=k;i1++)A[i1]=tmp[i1];}print(minn);putchar('\n');}return 0;
}