[SOJ #721]第三送分题(2019-11-14考试)/[CF675E]Trains and Statistic

题目大意

在一条直线上有(n)个点。在第(i)个点可以花费(1)的代价到达((i,a_i])中任意一点，用(S[i][j])表示从点(i)到点(j)的最少花费，求(sumlimits_{1leqslant i< jleqslant n}S[i][j])。(nleqslant10^5)

题解

若从点(i)开始，那么到((i,a_i])的代价为(1)，令(p)为((i,a_i])中(a_p)最大的点，则到((a_i,a_p])的代价为(2)。那么，若知道了点(sumlimits_{j=p+1}^nS[p][j])，那么(sumlimits_{j=i+1}^nS[i][j]=sumlimits_{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 << '
';
	return 0;
}