链接：戳这里
E. Trains and Statistic time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Vasya commutes by train every day. There are n train stations in the city, and at the i-th station it's possible to buy only tickets to stations from i + 1 to ai inclusive. No tickets are sold at the last station.
Let ρi, j be the minimum number of tickets one needs to buy in order to get from stations i to station j. As Vasya is fond of different useless statistic he asks you to compute the sum of all values ρi, j among all pairs 1 ≤ i < j ≤ n.
Input
The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of stations.
The second line contains n - 1 integer ai (i + 1 ≤ ai ≤ n), the i-th of them means that at the i-th station one may buy tickets to each station from i + 1 to ai inclusive.
Output
Print the sum of ρi, j among all pairs of 1 ≤ i < j ≤ n.
Examples
input
4
4 4 4
output
6
input
5
2 3 5 5
output
17
Note
In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is 6, so the answer is also 6.
Consider the second sample:
ρ1, 2 = 1
ρ1, 3 = 2
ρ1, 4 = 3
ρ1, 5 = 3
ρ2, 3 = 1
ρ2, 4 = 2
ρ2, 5 = 2
ρ3, 4 = 1
ρ3, 5 = 1
ρ4, 5 = 1
Thus the answer equals 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17.
题意：
n个车站,给出n-1个数ai,表示每个车站可以买到(i+1~ai)车站的票
定义f[i][j](i<j)为从第i个火车站到第j个火车站最少需要买多少票
问sum(f[i][j])和的最小值
思路：
dp状态方程：dp[i]=dp[m]+(n-i)+(a[i]-m) i<m<=a[i]<=a[m]<=n
dp[i]表示从第i个火车站到(i+1~n)至少需要买的火车票数量
从dp[m]可以推断出dp[i]的答案必须继承dp[m]的答案,这个m表示(i+1<=j<=a[i])里面a[j]的最大值
指的是我能从i买一张火车票到达m,然后m能去最远的地方表示我只需要继承dp[m],(显然当前的dp[m]为最优值),
就是我到了m这个火车站,那么剩下的最优买票肯定从dp[m]继承过来
至于为什么+(n-i)+(a[i]-m) (n-i)表示从i去每个火车站至少需要买一张票
但是到了m车站以后,记住是我现在就在m车站！！！dp[m]他肯定自己最优处理了这些(a[i]-m)的火车票 所以需要减去
线段树找出这个m
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int n;
int a[100100];
struct node{
int l,r,v;
}tr[500100];
void build(int root,int l,int r){
tr[root].l=l;
tr[root].r=r;
if(l==r) {
tr[root].v=l;
return ;
}
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
if(a[tr[root*2].v]>a[tr[root*2+1].v]) tr[root].v=tr[root*2].v;
else tr[root].v=tr[root*2+1].v;
}
int query(int root,int l,int r){
if(l<=tr[root].l && r>=tr[root].r)
return tr[root].v;
int mid=(tr[root].l+tr[root].r)/2;
if(r<=mid) return query(root*2,l,r);
else if(l>mid) return query(root*2+1,l,r);
else {
int f1=query(root*2,l,mid);
int f2=query(root*2+1,mid+1,r);
if(a[f1]>a[f2]) return f1;
else return f2;
}
}
ll dp[100100];
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++) scanf("%d",&a[i]);
a[n]=n-1;
build(1,1,n);
ll ans=0;
dp[n]=0;
for(int i=n-1;i>=1;i--){
int pos=query(1,i+1,a[i]);
///printf("%d %d %d ",i+1,a[i],pos);
dp[i]=dp[pos]+(ll)(n-i-(a[i]-pos));
ans+=dp[i];
}
cout<<ans<<endl;
return 0;
}