Luogu P5155

设$g_x$为从点$x$出发的期望，如果是在点$x$退出，那么显而易见$g_x = f(x)$，否则$g_x = \frac{g_{x-1} + g_{x + 1}}{2}$。所以将$g_{x}$画成折线图，就是一个上凸壳了，维护凸壳即可。

#include <iostream>
#include <cstdio>

#define MAX_N 100010
typedef long long ll;

int n, sta[MAX_N], tp;
ll f[MAX_N], res[MAX_N];

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &f[i]);
	for(int i = 0; i <= n + 1; i++){
		f[i] *= 100000;
		auto chk = [&](){
			return (f[sta[tp]] - f[sta[tp-1]]) * (i - sta[tp]) < (f[i] - f[sta[tp]]) * (sta[tp] - sta[tp-1]);
		};
		while(tp > 1 && chk()) tp--;
		sta[++tp] = i;
	}
	for(int i = 1; i < tp; i++){
		res[sta[i]] = f[sta[i]];
		for(int j = sta[i] + 1; j < sta[i+1]; j++)
			res[j] = (ll)((double)(f[sta[i+1]] - f[sta[i]]) * (j - sta[i]) / (sta[i+1] - sta[i]) + f[sta[i]]);
	}
	for(int i = 1; i <= n; i++)
		printf("%lld\n", res[i]);
	return 0;
}