BZOJ1492 [NOI2007] 货币兑换

2018 年 04 月 14 日发布.

Description

你有 $S$ 元钱。在第 $i$ 天你可以把 $x$ 元钱变成 $\frac{Rate_ix}{Rate_iA_i+B_i}$ 单位 A 金券和 $\frac{x}{Rate_iA_i+B_i}$ 单位 B 金券；或把 $a$ 单位 A 金券 $b$ 单位 B 金券变成 $A_ia+B_ib$ 元钱。

问 $n$ 天后你最多能持有多少元钱。 $n\leqslant10^6$ 。

Solution

显然我每次要么把现金全换成金券要么把金券全换成现金。

考虑 DP 。$f_i$ 表示第 $i$ 天结束时至多持有多少现金。

令 $\begin{cases}x_i=Rate_iy_i\\y_i=\frac{f_i}{Rate_iA_i+B_i}\end{cases}$ 表示我在这一天把现金换成金券时至多持有的 A/B 券数，那么有

$$f_i = \max\left(f_{i-1}, \max_{j=0}^{i-1}(A_ix_j+B_iy_j)\right)$$

这是一个显然的斜率优化式子（ $A_ix_j+B_iy_j$ 可以看做 $B_i$ 乘以“经过 $(x_i,y_i)$ 这个点的斜率为 $-\frac{A_i}{B_i}$ 的直线的斜率”）。~~可以单调队列~~

似乎不大对...因为 $x_i$ 和 $y_i$ 都不是递增的，没法单调队列维护凸包。~~平衡树维护凸包啊~~

考虑 CDQ 分治。具体的讲，首先我递归求出左边一半 $f$ ，然后把左边一半里的 $(x_i, y_i)$ 按横坐标排序，右边一半按斜率排序；然后 $O(n)$ 处理左边对右边的影响；然后递归求右边一半 $f$ 即可。

复杂度 $T(n)=2T(n/2)+O(n)$ ，可以解出 $T(n)=O(n\log n)$ 。

Code

#include <algorithm>
#include <cctype>
#include <cstdio>

const int N = 1000050;
const double eps = 1e-6;

int n;
double f[N];
struct Point{
  double Rate, A, B;
  double x, y, k;
  int id;
  inline friend bool operator<(const Point &a, const Point &b) {
    return a.k > b.k;
  }
}P[N];

inline double abs(double x) { return x < 0 ? -x : x; }

inline double CP(const Point &a, const Point &b, const Point &c) {
  // (b - a) x (c - a)
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline double calc(const Point &a, const Point &b) {
  return a.x * b.A + a.y * b.B;
}

inline bool cmp(const Point &a, const Point &b) {
  if (abs(a.x - b.x) <= eps) return a.y < b.y;
  return a.x < b.x;
}

void Solve(int l, int r) { // [l, r)
  if (r - l <= 1) {
    if (l != 0) f[l] = std::max(f[l], f[l - 1]);
    P[l].y = f[l] / (P[l].Rate * P[l].A + P[l].B);
    P[l].x = P[l].y * P[l].Rate;
    return;
  }

  int mid = (l + r) >> 1;
  static Point _tmp[N], CV[N];
  Point *tl = _tmp, *tr = _tmp + (mid - l);
  for (int i = l; i < r; ++i) *((P[i].id < mid ? tl : tr)++) = P[i];
  tl = _tmp;
  for (int i = l; i < r; ++i) P[i] = *(tl++);

  Solve(l, mid);

  int m = 0;
  for (int i = l; i < mid; ++i)
    if (i == l || abs(P[i].x - P[i - 1].x) > eps) {
      while (m > 1 && CP(CV[m - 2], CV[m - 1], P[i]) > 0) --m;
      CV[m++] = P[i];
    }
  for (int i = mid, j = 0; i < r; ++i) {
    while (j < m - 1 && calc(CV[j + 1], P[i]) > calc(CV[j], P[i])) ++j;
    f[P[i].id] = std::max(f[P[i].id], calc(CV[j], P[i]));
  }

  Solve(mid, r);

  tl = P + l, tr = P + mid;
  Point *res = _tmp;
  while (tl < P + mid || tr < P + r)
    if (tr == P + r || (tl != P + mid && cmp(*tl, *tr)))
      *(res++) = *(tl++);
    else
      *(res++) = *(tr++);
  for (tl = P + l, res = _tmp; tl != P + r; ++tl)
    *tl = *(res++);
}

int main() {
  scanf("%d%lf", &n, &f[0]);
  for (int i = 0; i < n; ++i) {
    scanf("%lf%lf%lf", &P[i].A, &P[i].B, &P[i].Rate);
    P[i].k = -P[i].A / P[i].B;
    P[i].id = i;
  }

  std::sort(P, P + n);
  Solve(0, n);
  printf("%.3lf\n", f[n - 1]);

  return 0;
}