题目大意:
在一条直线上有\(n\)个点。在第\(i\)个点可以花费\(1\)的代价到达\((i,a_i]\)中任意一点,用\(S[i][j]\)表示从点\(i\)到点\(j\)的最少花费,求\(\sum\limits_{1\leqslant i< j\leqslant n}S[i][j]\)。\(n\leqslant10^5\)
题解:
若从点\(i\)开始,那么到\((i,a_i]\)的代价为\(1\),令\(p\)为\((i,a_i]\)中\(a_p\)最大的点,则到\((a_i,a_p]\)的代价为\(2\)。那么,若知道了点\(\sum\limits_{j=p+1}^nS[p][j]\),那么\(\sum\limits_{j=i+1}^nS[i][j]=\sum\limits_{j=p+1}^nS[p][j]+(n-a_i)+(p-i)\)。就可以倒着求出每个点到后面每个点的代价和。
卡点:
无
C++ Code:
#include <cstdio>
#include <algorithm>
#include <iostream>
const int maxn = 1e5 + 10;
int n, a[maxn], S[maxn], top;
long long ans, f[maxn];
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n;
for (int i = 1; i < n; ++i) std::cin >> a[i];
f[n] = 0, S[top = 1] = n;
for (int i = n - 1; i; --i) {
int pos = *std::lower_bound(S + 1, S + top + 1, a[i], std::greater<int> ());
while (top && a[i] >= a[S[top]]) --top;
S[++top] = i, f[i] = f[pos] + n - a[i] + pos - i, ans += f[i];
}
std::cout << ans << '\n';
return 0;
}