BZOJ 1492
题意：金券交易所可以对$A 、B$两种金券进行交易。
接下来的$N$天内，第$i$天$A、B$分别具有单位价值$A_i,B_i$,每一天用户进行若干次如下操作:
1、卖出所有的金券
2、用所有的钱买入等价值的金券，买入的$A、 B$两种金券的比例为$\text{Rate}_i$
初始时用户拥有$S$元钱，问$N$天后用户最多拥有多少钱?
可以证明每次一定全卖或者全买，不严谨证明是有利可图就尽量做，否则就不做。
具体证明即设有$S$元钱，我们设卖出单位收益为$p$, 不卖单位收益为$q$，卖出比例$x$, 则收益为$S \cdot x \cdot p + S \cdot (1 - x) \cdot q=S(x(p-q)+ q)$
当$p-q \geq 0$时，取$x=1$有最大值
当$p-q \leq 0$时，取$x=0$有最大值
所以得证。
那么设$f(i)$为前$i$天的最大收益。
则
$$
f(i)=\max_\limits{1 \leq j \leq i-1}(f(i-1),A_ix_j+B_iy_j)
$$
其中$x_j, y_j$为最多能买到的$A,B$劵数量。
由
$$
\begin{cases}
f(j)=x_iA_j+y_iB_j \\
\frac{x_j}{y_j}=\text{Rate}_j
\end{cases}
$$
可算出$x_i, y_j$的值。
那么考虑斜率优化，我们可以得到
$$
y_j=-\frac{A_i}{B_i}x_j+\frac{f(i)}{B_i}
$$
但是这里$x$和斜率都不单调怎么办？
考虑动态维护上凸包。可以用平衡树来维护，即每次插入一个决策点，如果这个决策点和它$x$最近两个点连后形成下凸，则不用加这个决策点，否则向左找到一个最远的能形成凸包的，右边同理，然后将这两个点之间所有决策点删除，插入这个决策点，形成新的上凸包。可以用Splay来维护，也可以用Set
因为一个位置的决策集合是它前面的点，所以我们可以考虑CDQ分治。具体步骤为
若$l=r$则返回。
把左区间按编号把$≤mid$的分到左边，大于$mid$的分到右边。
分治左区间CDQ(l,mid)。
此时左区间横坐标有序，右区间斜率有序，所以用单调队列斜率优化DP。
分治右区间CDQ(mid+1,r)。
按$x$归并排序。
即左边构造好上凸包，用来更新右边的答案
有序情况具体情况如下
| 进入 | CDQ(l, M) |
CDQ(M + 1, r) |
合并 | |
|---|---|---|---|---|
| 左区间 | $k$ | $x$ | $x$ | $x$ |
| 右区间 | $k$ | $k$ | $x$ | $x$ |
| 所有 | $k$ | 无 | 无 | $x$ |
1、注意斜率不存在时INF的正负。
2、注意CDQ分治时q[i].id与i的区别
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
const db eps = 1e-10, INF = 1e17;
int n, st[MAXN], top;
db dp[MAXN];
struct data {
int id;
db a, b, r, k, x, y;
bool operator < (const data &rhs) const {
return k < rhs.k;
}
} q[MAXN], tmp[MAXN];
db getK(int a, int b) {return fabs(q[a].x - q[b].x) <= eps ? (q[a].y < q[b].y ? -INF : INF) : (q[a].y - q[b].y) / (q[a].x - q[b].x);}
void CDQ(int l, int r) {
if (l == r) { // [1, l - 1]处理完毕
dp[l] = max(dp[l], dp[l - 1]);
q[l].y = dp[l] / (q[l].a * q[l].r + q[l].b);
q[l].x = q[l].y * q[l].r;
return ;
}
int mid = (l + r) >> 1;
int t1 = l, t2 = mid + 1;
for (int i = l; i <= r; ++i) { // 分区间
if (q[i].id <= mid) {
tmp[t1++] = q[i];
} else tmp[t2++] = q[i];
}
for (int i = l; i <= r; ++i) q[i] = tmp[i];
CDQ(l, mid);
top = 0;
for (int i = l; i <= mid; ++i) { // 构造上凸包
while (top >= 2 && getK(i, st[top]) - getK(st[top], st[top - 1]) >= eps) --top;
st[++top] = i;
}
for (int i = mid + 1; i <= r; ++i) { // 求值
while (top >= 2 && getK(st[top], st[top - 1]) - q[i].k <= eps) --top;
int j = st[top];
dp[q[i].id] = max(dp[q[i].id], q[i].a * q[j].x + q[i].b * q[j].y);
}
CDQ(mid + 1, r);
t1 = l, t2 = mid + 1;
int cnt = 0;
while (t1 <= mid || t2 <= r) { // 按x归并
if (t2 > r || (t1 <= mid && q[t1].x <= q[t2].x)) {
tmp[++cnt] = q[t1++];
} else {
tmp[++cnt] = q[t2++];
}
}
for (int i = l; i <= r; ++i) q[i] = tmp[i - l + 1];
}
void clean() {
}
int solve() {
clean();
scanf("%d%lf", &n, &dp[0]);
for (int i = 1; i <= n; ++i) {
scanf("%lf%lf%lf", &q[i].a, &q[i].b, &q[i].r);
q[i].k = -q[i].a / q[i].b, q[i].id = i;
}
sort(q + 1, q + 1 + n);
CDQ(1, n);
printf("%.7f\n", dp[n]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
