BZOJ

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<i-1)$，则

$$A_i\cdot Rate_j \cdot F_j+B_i\cdot F_j>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.