[BZOJ 5483][Usaco2018 Dec]Balance Beam

显然,选择结束还是继续只和当前的位置有关。设当前位置为x,左边第一个选择结束的位置为l,右边第一个选择结束的位置为r。可以发现这一段上的期望收益是一个等差数列,而当前位置的期望收益就是(l, f_l)(r, f_r)的线段在x处的纵坐标。因此,最优的期望收益就是加入(0, 0)(n + 1, 0)(i, f_i)的上凸壳对应位置纵坐标的值。运算可以全程用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));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注