[USACO18DEC]Balance Beam P
热爱卡精度的你，为什么分数不取模？
既然不去模，那么拿到这个题先想想能不能乱搞过去。
设 \(f_{i,j}\) 表示 \(i\) 点出发至多走 \(j\) 次的最优期望报酬。当 \(j \rightarrow +\infty\) 时视为答案。转移为
\[f_{i,j} = \max\{f_{i, j - 1}, \frac{f_{i - 1, j - 1} + f_{i + 1,j - 1}}{2}\}
\]
然后开始画图手模，发现一个下凸包最后会变成一条线段。所以最后的形状就是开始的上凸包，结束。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T, typename... Rest>
inline void read(T &x, Rest&... rest) {
read(x), read(rest...);
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
constexpr int N = 1e5 + 10;
int n;
unsigned long long f[N];
int main() {
read(n);
for(int i = 1; i <= n; ++i) {
int x; read(x);
f[i] = x * 100000ll;
}
static int stk[N], top;
auto slope = [&](int x, int y) {
return 1.0 * (f[x] - f[y]) / (x - y);
};
stk[top = 1] = 0;
for(int i = 1; i <= n + 1; ++i) {
while(top > 1 && slope(i, stk[top]) > slope(stk[top], stk[top - 1]))
--top;
stk[++top] = i;
}
for(int i = 1; i < top; ++i) {
for(int j = stk[i] + 1; j < stk[i + 1]; ++j)
f[j] = ((stk[i + 1] - j) * f[stk[i]] + (j - stk[i]) * f[stk[i + 1]]) / (stk[i + 1] - stk[i]);
}
for(int i = 1; i <= n; ++i)
printf("%llu\n",f[i]);
return 0;
}