danihao123's Blog

[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~~），我直接把我向量集那题的二进制分组线段树搬了过来……（逃

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

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

[LibreOJ 2353][NOI2007]货币兑换

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器