这是道CDQ分治的例题：
$O(n^2)$的DP：
f [1]←S* Rate[1] / (A[1] * Rate[1] + B[1])
Ans←S
For i ← 2 to n
For j ←1 to i-1
x ← f [j] * A[i] + f [j] / Rate[j] * B[i]
If x> Ans
Then Ans ← x
End For
f [i] ← Ans* Rate[i] / (A[i] * Rate[i] + B[i])
End For
Print(Ans)
决策i是通过1～i-1之间的决策转移过来的，对于j,k∈[1,i-1]且决策k比决策j优当且仅当：
$$(f[j]-f[k])×A[i]+frac{f[j]}{Rate[j]-frac{f[k]}{Rate[k]}}×B[i]<0$$
不妨设$f[j]<f[k]$，$g[j]=frac{f[j]}{Rate[j]}$，那么
$$frac{g[j]-g[k]}{f[j]-f[k]}>-frac{a[i]}{b[i]}$$
斜率优化DP能用单调队列维护是因为右边的斜率是单调的，但这里$-frac{a[i]}{b[i]}$显然是不单调的，这时就需要在单调队列上二分。但因为每次插入的点的横坐标也不是单调的，我们就得建立一棵splay在线地向其中加点或询问
以f值为关键字建立splay，维护一个横坐标为f值，纵坐标为g值得上凸壳，时间复杂度为$O(nlog n)$
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double inf = 1e9;
const double eps = 1e-9;
const int N = 100003;
int n;
double f[N], A[N], B[N], Rate[N];
struct node *null;
struct node {
node *ch[2], *fa;
double lk, rk, x, y;
int id;
node(int num) {ch[0] = ch[1] = fa = null; lk = rk = x = y = 0; id = num;}
bool pl() {return fa->ch[1] == this;}
void setc(node *r, bool c) {this->ch[c] = r; if (r != null) r->fa = this;}
} *root;
namespace Splay {
void rotate(node *r) {
node *f = r->fa;
bool c = r->pl();
if (f == root) root = r, r->fa = null;
else f->fa->setc(r, f->pl());
f->setc(r->ch[!c], c);
r->setc(f, !c);
}
void splay(node *r, node *tar = null) {
for(; r->fa != tar; rotate(r))
if (r->fa->fa != tar) rotate(r->pl() == r->fa->pl() ? r->fa : r);
}
node *find(double x) {
if (root == null) return null;
node *r = root;
while (r != null) {
if (r->lk < x) r = r->ch[0];
else if (r->rk > x) r = r->ch[1];
else if (r->lk >= x && r->rk <= x) return r;
}
return r;
}
double get(node *a, node *b) {
if (fabs(a->x - b->x) < eps) return -inf;
else return (b->y - a->y) / (b->x - a->x);
}
node *getl(node *r) {
node *t = r->ch[0], *ans = t;
while (t != null) {
if (t->lk >= get(t, r)) ans = t, t = t->ch[1];
else t = t->ch[0];
}
return ans;
}
node *getr(node *r) {
node *t = r->ch[1], *ans = t;
while (t != null) {
if (get(r, t) >= t->rk) ans = t, t = t->ch[0];
else t = t->ch[1];
}
return ans;
}
void insert(node *t) {
if (root == null) {
root = t;
root->lk = inf;
root->rk = -inf;
return;
}
node *r = root;
while (r != null) {
if (t->x < r->x) {
if (r->ch[0] == null) {r->setc(t, 0); break;}
else r = r->ch[0];
} else {
if (r->ch[1] == null) {r->setc(t, 1); break;}
else r = r->ch[1];
}
}
splay(t);
if (t->ch[0] != null) {
node *tl = getl(t);
splay(tl, root);
tl->ch[1] = null;
tl->rk = t->lk = get(tl, t);
} else
t->lk = inf;
if (t->ch[1] != null) {
node *tr = getr(t);
splay(tr, root);
tr->ch[0] = null;
tr->lk = t->rk = get(t, tr);
} else
t->rk = -inf;
if (t->lk < t->rk) {
node *cl = t->ch[0], *cr = t->ch[1];
if (cl == null && cr == null) //其实删点根本不用这么麻烦，不用判断左边是否为空，若左边为空那么t->lk<t->rk的判断就过不了，这是fqk打野提醒我的QAQ
root = null;
else if (cl == null) {
root = cr;
cr->fa = null;
cr->lk = inf;
} else if (cr == null) {
root = cl;
cl->fa = null;
cl->rk = -inf;
} else {
root = cl;
cl->fa = null;
cl->setc(cr, 1);
cl->rk = cr->lk = get(cl, cr);
}
}
}
}
int main() {
scanf("%d%lf", &n, &f[0]);
for(int i = 1; i <= n; ++i) scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]);
null = new node(0); *null = node(0); root = null;
for(int i = 1; i <= n; ++i) {
node *j = Splay::find(-A[i] / B[i]);
f[i] = max(f[i - 1], j->x * A[i] + j->y * B[i]);
node *r = new node(i);
r->y = f[i] / (A[i] * Rate[i] + B[i]);
r->x = r->y * Rate[i];
Splay::insert(r);
}
printf("%.3lf
", f[n]);
return 0;
}
splay好写好调！但是还是得学CDQ分治啊！！！
CDQ分治利用预处理排序，使原先的序列的询问的斜率有序，然后处理左半边，用左半边更新右半边，再处理右半边，这样因为询问的斜率有序，就可以用单调队列或单调栈来维护了，复杂度也是$O(nlog n)$，论文里讲得很清楚啊。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100003;
const double inf = 1e9;
const double eps = 1e-9;
struct node {
double q, a, b, rate, k; int id;
} q[N], qq[N];
struct Point {
double x, y;
bool operator < (const Point &a) const {
return (x < a.x) || (fabs(x - a.x) < eps && y < a.y);
}
} p[N], pp[N];
double get(int x, int y) {
if (fabs(p[x].x - p[y].x) < eps) return -inf;
return (p[x].y - p[y].y) / (p[x].x - p[y].x);
}
int st[N], n;
double f[N];
void solve(int l, int r) {
if (l == r) {
f[l] = max(f[l - 1], f[l]);
p[l].y = f[l] / (q[l].a * q[l].rate + q[l].b);
p[l].x = p[l].y * q[l].rate;
return;
}
int mid = (l + r) >> 1, h = l, t = mid + 1;
for(int i = l; i <= r; ++i)
if (q[i].id <= mid) qq[h++] = q[i];
else qq[t++] = q[i];
for(int i = l; i <= r; ++i) q[i] = qq[i];
solve(l, mid);
int top = 0;
for(int i = l; i <= mid; ++i) {
while (top >= 2 && get(i, st[top]) > get(st[top], st[top - 1])) --top;
st[++top] = i;
}
t = 1;
for(int i = r; i > mid; --i) {
while (t < top && q[i].k < get(st[t], st[t + 1])) ++t;
f[q[i].id] = max(f[q[i].id], p[st[t]].x * q[i].a + p[st[t]].y * q[i].b);
}
solve(mid + 1, r);
h = l; t = mid + 1;
for(int i = l; i <= r; ++i)
if ((p[h] < p[t] || t > r) && h <= mid) pp[i] = p[h++];
else pp[i] = p[t++];
for(int i = l; i <= r; ++i) p[i] = pp[i];
}
bool cmp(node A, node B) {return A.k < B.k;}
int main() {
scanf("%d%lf", &n, &f[0]);
for(int i = 1; i <= n; ++i) {
scanf("%lf%lf%lf", &q[i].a, &q[i].b, &q[i].rate);
q[i].k = -q[i].a / q[i].b;
q[i].id = i;
}
sort(q + 1, q + n + 1, cmp);
solve(1, n);
printf("%.3lf
", f[n]);
return 0;
}
省队集训期间我充分展现出了自己的弱QAQ(为什么不说发现自己的弱呢，因为我很久以前就发现了TwT)继续努力～后天就要回新校颓文化课了，下一个月好好搞文化课，年级里的排名不能再退步了。希望期末考试能取得较大的进步，毕竟这是我第一次准备认认真真颓文化课QwQ←滚粗狗的无奈
2016-07-11期末挂惨了TwT，比以前任何一次都惨_(:з」∠)_之前的flag too naive！