设$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;
}