CF675E Trains and Statistic

一、题目

点此看题

二、解法

首先由一个结论：对于一个往后走的 $i$，找到 $[i+1,a_i]$中 $a_k$最大的 $k$，那么 $[i+1,a_i]$直接跳，后面的先跳在 $k$最优。其正确性显然，因为 $k$是够得最远的（手最长的）。

那么设 $f[i]=\sum_{j=i+1}^np[i][j]$，从后往前处理，找到对于 $i$的这个 $k$，转移：
$f[i]=f[k]+(n-i)-(a[i]-k)$然后写一个 $rmq$就行了。

#include <cstdio>
#include <cmath>
#define int long long
const int M = 100005;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,ans,a[M],dp[M][20],f[M];
int Max(int x,int y)
{return a[x]>a[y]?x:y;
}
int ask(int l,int r)
{int k=log2(r-l+1);return Max(dp[l][k],dp[r-(1<<k)+1][k]);
}
signed main()
{n=read();for(int i=1;i<n;i++){a[i]=read();dp[i][0]=i;}for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)dp[i][j]=Max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);for(int i=n-1;i>=1;i--){int k=ask(i+1,a[i]);if(a[i]>=n) f[i]=n-i;else f[i]=f[k]+(n-i)-(a[i]-k);ans+=f[i];}printf("%lld\n",ans);
}