【题解】[USACO18DEC] Balance Beam P

题目链接：[USACO18DEC] Balance Beam P

题意：

给定长度为 $n$ 的序列 $\{a_n\}$，初始有一个棋子在位置 $i$。每一轮可以选择结束游戏，获得当前所在节点的分数 $a_i$，也可以选择继续游戏，则棋子等概率移至 $i-1,i+1$，若走出序列则游戏结束，分数为 $0$。
对于 $i\in[1,n]$，求出初始棋子在 $i$，能得到的最大期望分数。
$1\le n\le 10^5$。

好玩啊这题。

设 $E(x)$ 表示当前棋子在 $x$，所能得到的最大期望分数。那么显然：

$$ E(x)=\max(a_x,\dfrac{1}{2}(E(x-1)+E(x+1))) $$

好像不是太好入手，那不妨从我们知道的东西来考虑：我们知道所有 $a_x$。

考虑一个集合 $S=\{x\ |\ E(x)=a_x\}$，那么对于集合中相邻两个元素 $p,q\ (p<q)$，所有 $x\in(p,q)$ 有 $E(x)-E(x-1)=E(x+1)-E(x)$。

因此 $E(x)=\dfrac{(x-p)\times a_p+(q-x)\times a_q}{q-p}$，这恰好就是过 $(p,a_p),(q,a_q)$ 两点的函数在 $x$ 处的取值。

所以答案就是点集 $(i,a_i)$ 的上凸壳，时间复杂度 $\mathcal{O}(n)$。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m;
int s[MAXN], stk[MAXN], top, p = 1;
double Ans[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

double slope(int a, int b) { return 1. * (s[a] - s[b]) / (a - b); }

signed main () {
#ifdef FILE
    freopen("P5155.in", "r", stdin);
    freopen("P5155.out", "w", stdout);
#endif
    read(n);
    for(int i = 1; i <= n; ++i) read(s[i]), s[i] *= 1e5;
    for(int i = 0; i <= n + 1; ++i) {
        while(top > 1 && slope(stk[top - 1], stk[top]) < slope(stk[top - 1], i)) top--;
        stk[++top] = i;
    }
    for(int i = 1; i <= n; ++i) {
        while(stk[p + 1] <= i) ++p;
        Ans[i] = slope(stk[p], stk[p + 1]) * (i - stk[p]) + s[stk[p]];
        printf("%lld\n", (int)Ans[i]);
    }
    return 0;
}