emmm做了一下这道神题……（我可能是少有的用动态凸包苟的？）

首先DP方程长这样：

\[f_i = max(f_{i - 1}, f_j\cdot\frac{A_iR_j+B_i}{A_jR_j+B_j})\]

然后这个方程炒鸡复杂……首先\(f_{i - 1}\)不要管了，然后设\(a_i = \frac{f_i}{A_iR_i + B_i}\)。在xjb推了一番之后我们终于得到了截距式……

\[-a_j R_j \frac{A_i}{B_i} + \frac{f_i}{B_i} = a_j\]

但是这玩意太毒瘤了……斜率不可能单调的，这还好，在凸壳上二分/三分一下即可。但问题在于，横坐标也不单调……

这个时候就需要动态维护凸包了（其实是我不会CDQ），我直接把我向量集那题的二进制分组线段树搬了过来……（逃

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <climits>
#include <deque>
#include <cassert>
using R = double;
const R eps = 1e-8;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x > 0.00) {
      return 1;
    } else {
      return -1;
    }
  }
}

struct Point {
  R x, y;
  Point(R qx = 0, R qy = 0) {
    x = qx; y = qy;
  }
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(b.x - a.x, b.y - a.y);
}
Vector operator *(const Vector &a, R lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(R lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline R dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline R times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
  if(sign(a.x - b.x) == 0) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
  std::sort(P + 1, P + 1 + L, cmp);
  for(int i = 1; i <= L; i ++) {
    if(i != 1 && sign(P[i].x - P[i - 1].x) == 0) continue;
    while(bot.size() > 1 && sign(times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0) {
      bot.pop_back();
    }
    bot.push_back(P[i]);
  }
  for(int i = L; i >= 1; i --) {
    if(i != L && sign(P[i].x - P[i + 1].x) == 0) continue;
    while(top.size() > 1 && sign(times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0) {
      top.pop_back();
    }
    top.push_back(P[i]);
  }
  std::reverse(top.begin(), top.end());
}

const int maxn = 1000005;
const int N = 1000000;
const int maxno = maxn << 2;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
  static Point tmp[maxn];
  const int lc = o << 1, rc = o << 1 | 1;
  const bool used = zen[o];
  zen[o] = (zen[lc] && zen[rc]);
  if(zen[o] != used) {
    std::copy(P + L, P + R + 1, tmp + 1);
    int len = R - L + 1;
    andrew(tmp, len, bot[o], top[o]);
  }
}
void modify(int o, int L, int R, const int &p, const Point &v) {
  if(L == R) {
    zen[o] = true;
    P[L] = v;
    bot[o].push_back(v); top[o].push_back(v);
  } else {
    const int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o, L, R);
  }
}
inline R calc_ans(R k, const Point &v) {
  return v.y - k * v.x;
}
inline R search(const std::vector<Point> &vec, const R &k) {
  int l = 0, r = vec.size() - 1;
  while(r - l > 2) {
    int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
    if(sign(calc_ans(k, vec[lm]) - calc_ans(k, vec[rm])) == 1) {
      r = rm;
    } else {
      l = lm;
    }
  }
  R ans = INT_MIN;
  for(int i = l; i <= r; i ++) {
    ans = std::max(ans, calc_ans(k, vec[i]));
  }
  return ans;
}
R query(int o, int L, int R, const int &ql, const int &qr, const double &k) {
  if(ql <= L && R <= qr) {
    return search(top[o], k);
  } else {
    int M = (L + R) / 2;
    double ans = INT_MIN;
    if(ql <= M) {
      ans = std::max(ans, query(o << 1, L, M, ql, qr, k));
    }
    if(qr > M) {
      ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, k));
    }
    return ans;
  }
}

int n, s;
R A[maxn], B[maxn], Rate[maxn];
R f[maxn];
R dp() {
  static double a[maxn];
  f[0] = s; f[1] = s; a[1] = f[1] / (A[1] * Rate[1] + B[1]);
  modify(1, 1, n, 1, Point(a[1] * Rate[1], a[1]));
  for(int i = 2; i <= n; i ++) {
    f[i] = query(1, 1, n, 1, i - 1, -A[i] / B[i]) * B[i];
    f[i] = std::max(f[i], f[i - 1]);
    a[i] = f[i] / (A[i] * Rate[i] + B[i]);
    if(i < n) modify(1, 1, n, i, Point(a[i] * Rate[i], a[i]));
  }
  return f[n];
}

int main() {
  scanf("%d%d", &n, &s);
  for(int i = 1; i <= n; i ++) {
    scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]);
  }
  printf("%.3lf\n", dp());
  return 0;
}

• 相关文章
• 全局相关文章