vijos P1508 / BZOJ 1492
膜拜了这么久的cdq分治，终于有机会亲自来写了。虽然这个思想很好理解，先做前一半，计算前一半对后一半的影响，再做后一半。但是由于我这个傻Ⅹ，以前既没有做过斜率优化，也没有做过维护凸包之类，花了好久时间捣鼓具体做法，而且理解思路后写起来还是有点难度的。
主要网上的解题各有各的思路，有的是F数组存最多多少B券，有的是存最多多少A券，虽然大同小异，但是一开始我没意识到所以orz了。
参考资料：
《从Cash谈一类分治算法的应用》——cdq
同时，我也很大程度上参考了这里的代码。=v=好不容易找了一个易读的C++代码…差不多就是翻译了过来，我的程序里写了“//？”是修改过的。
这么神的题一定要好好温习，同时也要好好学splay啊，至今没有成功码过一次QAQ
program cash;
//orz cdq
const eps=0.000000001;
maxn=;
type typeq=record
k,a,b,r:real;
pos:longint;
end;
typep=record
x,y:real;
end;
var i,j,n,s:longint;
//a,b,r:array[..] of longint;
f:array[..maxn] of real;
q,nq:array[..maxn] of typeq;
p,np:array[..maxn] of typep;
st:array[..maxn] of longint;
function max(a,b:real):real;
begin
if a>b then exit(a) else exit(b);
end; procedure qsort(l,r:longint);
var i,j:longint;
mid:real;
temp:typeq;
begin
i:=l;j:=r;mid:=q[(l+r) div ].k;
while i<=j do
begin
while q[i].k<mid do inc(i);
while q[j].k>mid do dec(j);
if i<=j then
begin
temp:=q[i];q[i]:=q[j];q[j]:=temp;
inc(i);dec(j);
end;
end;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end; function getk(a,b:longint):real;
begin
if a= then exit(-maxlongint+);
if b= then exit(maxlongint);
if (p[a].x-p[b].x<=eps) and (p[a].x-p[b].x>=-eps) then exit(-maxlongint+);
exit((p[a].y-p[b].y)/(p[a].x-p[b].x));
end; procedure solve(l,r:longint);
var mid,l1,l2,top,i,j:longint;
begin
if l=r then
begin
f[l]:=max(f[l-],f[l]);
p[l].y:=f[l]/(q[l].a*q[l].r+q[l].b);
p[l].x:=p[l].y*q[l].r;
exit;
end;
mid:=(l+r) div ;l1:=l;l2:=mid+;
for i:=l to r do
if q[i].pos<=mid then
begin
nq[l1]:=q[i];inc(l1); //?
end
else
begin
nq[l2]:=q[i];inc(l2); //?
end;
for i:=l to r do q[i]:=nq[i];
solve(l,mid);
top:=;
for i:=l to mid do
begin
while (top>=) and (getk(i,st[top])+eps>getk(st[top],st[top-])) do dec(top);
inc(top);st[top]:=i;
end;
j:=;
for i:=r downto mid+ do //update
begin
while (j<top) and (q[i].k<getk(st[j],st[j+])+eps) do inc(j);
f[q[i].pos]:=max(f[q[i].pos],p[st[j]].x*q[i].a+p[st[j]].y*q[i].b);
end;
solve(mid+,r);
l1:=l;l2:=mid+;
for i:=l to r do //?
if ((p[l1].x<p[l2].x) or (l2>r)) and (l1<=mid) then
begin
np[i]:=p[l1];inc(l1);
end
else
begin
np[i]:=p[l2];inc(l2);
end;
for i:=l to r do
p[i]:=np[i];
end; begin{main}
readln(n,f[]);
for i:= to n do
begin
readln(q[i].a,q[i].b,q[i].r);
q[i].k:=-q[i].a/q[i].b;
q[i].pos:=i;
end;
qsort(,n); //sort array q[i].k
solve(,n); //cdq solve
writeln(f[n]::);
end.
Cash
测试数据 #0: Accepted, time = 0 ms, mem = 12876 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 12876 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 12876 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 12876 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 12876 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 12876 KiB, score = 10
测试数据 #6: Accepted, time = 296 ms, mem = 12880 KiB, score = 10
测试数据 #7: Accepted, time = 312 ms, mem = 12880 KiB, score = 10
测试数据 #8: Accepted, time = 578 ms, mem = 12876 KiB, score = 10
测试数据 #9: Accepted, time = 609 ms, mem = 12876 KiB, score = 10
Accepted, time = 1810 ms, mem = 12880 KiB, score = 100