vijos P1508 / BZOJ 1492
膜拜了这么久的cdq分治,终于有机会亲自来写了。虽然这个思想很好理解,先做前一半,计算前一半对后一半的影响,再做后一半。但是由于我这个傻Ⅹ,以前既没有做过斜率优化,也没有做过维护凸包之类,花了好久时间捣鼓具体做法,而且理解思路后写起来还是有点难度的。
主要网上的解题各有各的思路,有的是F数组存最多多少B券,有的是存最多多少A券,虽然大同小异,但是一开始我没意识到所以orz了。
参考资料:
《从Cash谈一类分治算法的应用》——cdq
同时,我也很大程度上参考了这里的代码。=v=好不容易找了一个易读的C++代码…差不多就是翻译了过来,我的程序里写了“//?”是修改过的。
这么神的题一定要好好温习,同时也要好好学splay啊,至今没有成功码过一次QAQ
program cash; //orz cdq const eps=0.000000001; maxn=100010; 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[1..100000] of longint; f:array[0..maxn] of real; q,nq:array[1..maxn] of typeq; p,np:array[1..maxn] of typep; st:array[1..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 2].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=0 then exit(-maxlongint+1); if b=0 then exit(maxlongint); if (p[a].x-p[b].x<=eps) and (p[a].x-p[b].x>=-eps) then exit(-maxlongint+1); 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-1],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 2;l1:=l;l2:=mid+1; 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:=0; for i:=l to mid do begin while (top>=2) and (getk(i,st[top])+eps>getk(st[top],st[top-1])) do dec(top); inc(top);st[top]:=i; end; j:=1; for i:=r downto mid+1 do //update begin while (j<top) and (q[i].k<getk(st[j],st[j+1])+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+1,r); l1:=l;l2:=mid+1; 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[0]); for i:=1 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(1,n); //sort array q[i].k solve(1,n); //cdq solve writeln(f[n]:0:3); end.
测试数据 #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
[NOI2007 Day1] 货币兑换 Cash,布布扣,bubuko.com
原文:http://www.cnblogs.com/Sky-Grey/p/3819297.html