显然，选择结束还是继续只和当前的位置有关。设当前位置为，左边第一个选择结束的位置为，右边第一个选择结束的位置为。可以发现这一段上的期望收益是一个等差数列，而当前位置的期望收益就是到的线段在处的纵坐标。因此，最优的期望收益就是加入和后的上凸壳对应位置纵坐标的值。运算可以全程用long long完成，避免了精度误差。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 1e5 + 10;

struct Point
{
    ll x, y;
    Point() {}
    Point(ll x, ll y) : x(x), y(y) {}
    Point operator-(const Point &rhs) const { return Point(x - rhs.x, y - rhs.y); }
};

ll cross(const Point &a, const Point &b)
{
    return a.x * b.y - a.y * b.x;
}

int n, top;
ll f[MAX_N];
Point convex[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++)
    {
        convex[++top] = Point(i, f[i]);
        while (top >= 3 && cross(convex[top - 1] - convex[top - 2], convex[top] - convex[top - 2]) >= 0)
            convex[top - 1] = convex[top], top--;
    }
    int cur = 1;
    for (int i = 1; i <= n; i++)
    {
        if (convex[cur + 1].x <= i) cur++;
        printf("%lld\n", ((convex[cur + 1].x - i) * convex[cur].y + (i - convex[cur].x) * convex[cur + 1].y) * 100000 / (convex[cur + 1].x - convex[cur].x));
    }
}