Codeforces Round #353 (Div. 2) E. Trains and Statistic

n 個の駅があり、i 番目の駅からは i+1..a[i] の駅に移動可能である。

ρ(i,j) を駅 i から駅 j への最短ステップ数とする。すべての i<j に対する ρ(i,j) の総和を求めよ。

とする。dp[i+1]..dp[n-1] が求まっていれば、ここから dp[i] を計算できる。

i→i+1..a[i] は 1 ステップで到達できる。

$$ dp[i] += a[i] - (i+1) + 1 $$

a[i]+1 以降に行くには、i+1..a[i] のうち最も右に飛べる駅を経由するのが最適であるはず。最大の駅を M とすると、

$$ dp[i] += dp[M] + (n-1) - (M+1) + 1$$

M+1..a[i] を余分にカウントしてしまったため、引いておく。

$$ dp[i] -= 2(a[i] - (M+1) + 1) $$

データ構造で DP 加速かなと思ったのが運の尽き。