题目链接：http://codeforces.com/contest/675/problem/E
题意：你可以从第 i 个车站到 [i + 1, a[i]] 之间的车站花一张票。p[i][j]表示从 i 到 j 最少花费多少张票，问你 ∑p[i][j] (1<=i<j<=n) 是多少。
题解：不妨设a[n]=n，dp[i]表示i<j<=n的所有情况和。然后要知道从第 i 个车站到 [i + 1, a[i]] 之间的车站只花一张票那么到a[i]以后的车站，
所需要的最小值肯定是找到（1～a[i]）之间的最大值a[m],m表示下表介于1～a[i]。然后再通过a[m]来进行转移。
dp显然要从n-1往前推。然后dp[i]=n-i+dp[m]-(a[i]-m)，解释一下这个转移方程。m就是上面解释的。然后n-i表示从i点出来至少要花点n-i张
票。然后再加上dp[m]将最优的状态转移过来，还要剪去(a[i]-m)由于从i到大于a[i]之后的点不需要经过m~a[i]而经过m~a[i]点所需要的票数dp[m]
已经统计过了。所以要减去重复的。
#include <iostream>
#include <cstring>
using namespace std;
const int M = 1e5 + 10;
long long a[M] , dp[M];
struct TnT {
int l , r;
int pos ;
long long val;
}T[M << 2];
void push_up(int i) {
if(T[i << 1].val < T[(i << 1) | 1].val) {T[i].val = T[(i << 1) | 1].val , T[i].pos = T[(i << 1) | 1].pos;}
else {T[i].val = T[i << 1].val , T[i].pos = T[i << 1].pos;}
}
void build(int i , int l , int r) {
int mid = (l + r) >> 1;
T[i].l = l , T[i].r = r;
if(l == r) {
T[i].pos = l , T[i].val = a[l];
return ;
}
build(i << 1 , l , mid);
build((i << 1) | 1 , mid + 1 , r);
push_up(i);
}
pair<long long , int> query(int i , int l , int r) {
int mid = (T[i].l + T[i].r) >> 1;
if(T[i].l == l && T[i].r == r) {
return make_pair(T[i].val , T[i].pos);
}
push_up(i);
if(mid < l) return query((i << 1) | 1 , l , r);
else if(mid >= r) return query(i << 1 , l , r);
else {
pair<int , int>l1 = query(i << 1 , l , mid) , l2 = query((i << 1) | 1 , mid + 1 , r);
if(l1.first < l2.first) return l2;
return l1;
}
}
int main() {
int n;
cin >> n;
for(int i = 1 ; i <= n - 1 ; i++) {
cin >> a[i];
}
a[n] = n;
build(1 , 1 , n);
memset(dp , 0 , sizeof(dp));
long long ans = 0;
for(int i = n - 1 ; i >= 1 ; i--) {
int m = query(1 , i + 1 , (int)a[i]).second;
dp[i] += dp[m] + (n - i) - (a[i] - m);
ans += (long long)dp[i];
}
cout << ans << endl;
return 0;
}