BZOJ 1492

Orz CDQ

传送门

设$f_i$为第$i$天能获得的最大钱数,$F_i$为第$i$天持有的最大的$B$券数目,则

$$F_i=\frac{f_i}{A_i\times Rate_i+B_i}$$

$$f_i=max\lbrace f_{i-1},A_i\cdot Rate_j \cdot F_j+B_i\cdot F_j\rbrace (1\leq j<i)$$
($f_0$即为初始钱数)

若决策$j$优于决策$k(1\leq j,k A_i\cdot Rate_k \cdot F_k+B_i\cdot F_k$$
$$A_i(F_j\cdot Rate_j-F_k\cdot Rate_k)>-B_i(F_j-F_k)$$
$$\frac{F_j-F_k}{F_j\cdot Rate_j-F_k\cdot Rate_k}>-\frac{A_i}{B_i}$$

设$G_i=F_i\cdot Rate_i$
$$\frac{F_j-F_k}{G_j-G_k}>-\frac{A_i}{B_i}$$

左边那一坨就是$(G_j,F_j),(G_k,F_k)$两点连线的斜率
$$f_i=max(f_{i-1},max\lbrace A_i\cdot G_j+B_i\cdot F_j\rbrace) (1\leq j<i)$$

实际上就是求所有$j\in [1,i)$中的点$(G_j,F_j)$代入直线$A_i\cdot x+B_i\cdot y+d=0$后最小的$d$(最大的$-d$)

也就是说拿这条直线一点点往下移,从上往下碰到的第一个点$(G_j,F_j)$使得截距最大的就是答案,而这个点显然是在凸包上的

$p14y 2333Splay的写法有空了再慢慢写(UPD:已弃坑),先贴CDQ分治的…

具体搞法大概是这个姿势:

  • 首先把所有询问按$-\frac{A_i}{B_i}$递减排序(斜率由近似水平逐渐顺时针变到近似垂直,这样好切凸包)
  • 定义一个$Solve(l,r)$函数,然后分成$Solve(l,mid)$与$Solve(mid+1,r)$
  • 对于$Solve(l,mid)$,继续递归处理,然后搞一个$(l,mid)$的上凸壳来更新$(mid+1,r)$的决策
  • 递归$Solve(mid+1,r)$

Tips

每个$Solve$过程在更新答案后需要把区间里的询问先回复到原顺序依次处理

$Solve$结束时把$(l,r)$里的按照$F$值排序,使$F$保持递增,好更新后面的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
program bzoj_1492;
const eps=1e-6;
type rec=record a,b,r,k,f,g:extended; id:longint; end;
var p,t:array[0..110000]of rec;
f:array[0..110000]of extended;
s:array[1..110000]of longint;
n,i,top:longint;
function max(a,b:extended):extended;
begin
if a>b then exit(a) else exit(b);
end;
function k(a,b:longint):extended;
begin
if b=0 then exit(-1e20);
if abs(p[a].g-p[b].g)<eps then exit(1e20);
exit((p[a].f-p[b].f)/(p[a].g-p[b].g));
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,t:rec;
begin
i:=l;
j:=r;
mid:=p[(l+r)>>1];
repeat
while p[i].k>mid.k do inc(i);
while p[j].k<mid.k do dec(j);
if i<=j then
begin
t:=p[i];
p[i]:=p[j];
p[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure solve(l,r:longint);
var l1,l2,mid,i,j:longint;
begin
if l=r then
begin
f[l]:=max(f[l],f[l-1]);
p[l].f:=f[l]/(p[l].a*p[l].r+p[l].b);
p[l].g:=p[l].f*p[l].r;
exit;
end;
mid:=(l+r)>>1;
l1:=l;
l2:=mid+1;
for i:=l to r do if p[i].id<=mid then
begin
t[l1]:=p[i];
inc(l1);
end else
begin
t[l2]:=p[i];
inc(l2);
end;
for i:=l to r do p[i]:=t[i];
solve(l,mid);
top:=0;
for i:=l to mid do
begin
while(top>1)and(k(s[top-1],s[top])<k(s[top],i)+eps) do dec(top);
inc(top);
s[top]:=i;
end;
inc(top);
s[top]:=0;
j:=1;
for i:=mid+1 to r do
begin
while (j<top)and(k(s[j],s[j+1])>p[i].k+eps) do inc(j);
f[p[i].id]:=max(f[p[i].id],p[s[j]].g*p[i].a+p[s[j]].f*p[i].b);
end;
solve(mid+1,r);
l1:=l;
l2:=mid+1;
for i:=l to r do
if ((((abs(p[l1].g-p[l2].g)<eps)and(p[l1].f<p[l2].f))or(p[l1].g<p[l2].g))or(l2>r))and(l1<=mid) then
begin
t[i]:=p[l1];
inc(l1);
end else
begin
t[i]:=p[l2];
inc(l2);
end;
for i:=l to r do p[i]:=t[i];
end;
begin
readln(n,f[0]);
for i:=1 to n do with p[i] do
begin
readln(a,b,r);
k:=-a/b;
id:=i;
end;
qsort(1,n);
solve(1,n);
writeln(f[n]:0:3);
end.