首页 > 代码库 > [NOI2007 Day1] 货币兑换 Cash
[NOI2007 Day1] 货币兑换 Cash
vijos P1508 / BZOJ 1492
膜拜了这么久的cdq分治，终于有机会亲自来写了。虽然这个思想很好理解，先做前一半，计算前一半对后一半的影响，再做后一半。但是由于我这个傻Ⅹ，以前既没有做过斜率优化，也没有做过维护凸包之类，花了好久时间捣鼓具体做法，而且理解思路后写起来还是有点难度的。
主要网上的解题各有各的思路，有的是F数组存最多多少B券，有的是存最多多少A券，虽然大同小异，但是一开始我没意识到所以orz了。
参考资料：
《从Cash谈一类分治算法的应用》——cdq
《cdq分治相关》
同时，我也很大程度上参考了这里的代码。=v=好不容易找了一个易读的C++代码…差不多就是翻译了过来，我的程序里写了“//？”是修改过的。
这么神的题一定要好好温习，同时也要好好学splay啊，至今没有成功码过一次QAQ
program cash;//orz cdqconst 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