[LibreOJ 2353][NOI2007]货币兑换
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; }