[USACO18DEC]Balance Beam P

热爱卡精度的你，为什么分数不取模？

既然不去模，那么拿到这个题先想想能不能乱搞过去。

设 \(f_{i,j}\) 表示 \(i\) 点出发至多走 \(j\) 次的最优期望报酬。当 \(j \rightarrow +\infty\) 时视为答案。转移为

然后开始画图手模，发现一个下凸包最后会变成一条线段。所以最后的形状就是开始的上凸包，结束。

#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;
}