注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1492】【Noi2007】【货币兑换Cash】  

2014-04-14 16:55:04|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出两种货币每一天的价格,以及每一天能买入货币的比例,和一开始拥有的RMB数,求最大获利。

    0.0首先咱们可以发现,最好的策略显然是要么一次性卖出去,要么一次性买进来。(为什么是这个0.0咱会说咱是看样例猜的么)因为假设某天股票价格便宜,赶紧用所有钱买进来显然不差于以后某一天用剩下的钱买进来,同理卖出去也是一样的。所以咱们需要考虑的决策只有两个,1.某一天心情大好全部买进去。2.某一天全部卖掉获得利润。

    那么第一个算法就出来了,那就是搜索,但是这个的效率太低了,注意到咱们实际上容易搜索到很多重复的问题,咱们这里可以用dp来去掉这些重复的地方。一开始想了个很 ,b的dp方程,发现自己的感觉非常难写。然后去看了一下别人的dp方程... dp方程君 
    然后咱们设 f[i]表示某一天能够得到的最大钱数(实际上也就包括了货币的价值,因为每一天咱们实际上都可以把这些货币卖出去),那么对于f[i],咱们考虑从之前的某一天来进行转移,转移有两种,一种是在过去的某一天用那一天的最大获利(f[j])尽可能多地买入货币,然后在今天卖出去,一种是什么都不做,就用昨天的最大获利作为自己的。
    即  f[i]=max(f[i-1],x[j]*a[i]+y[j]*b[i])(j<=i-1)
    这个不加优化的话可以拿60分。0.0

    然后就需要优化之,实际上咱们需要优化的就是后一部分:
    max(x[j]*a[i]+y[j]*b[i]),(a[i],b[i]为已知数,不妨看做a,b算了)
 = max(a*x[j]+b*y[j])
    这个咱们来看看,两个决策j,k且j<k,咱们知道a>0,b>0,x>0,y>0如果有
      a*x[j]+b*y[j]<a*x[k]+b*y[k]
  =>a*(x[j]-x[k])<b*(y[k]-y[j])
  =>-a/b>(y[k]-y[j])/(x[k]-x[j])

    即如果某个点k的决策比j的优(j<k),那么就有它们的斜率<-a/b,而显然最优的那个点是 对于前面的点,它们的斜率都<-a/b,后面的点都满足斜率>=-a/b,其实这个就是维护一个凸包!!!

    如果上面的这种说法不太明显的话,可以去看看上面的链接的dp方程君,他(orz oimaster!!)描述了另外一种理解。

    然后关于维护凸壳,其实才是咱想做的。...一直没写,想写(被虐)一次。

    这里有个斜率优化的资料咱非常喜欢:斜率优化的资料
    
    咱们把所有的点按照横坐标排序,然后维护一个凸壳(实际上就是凸包了咱会乱说???)(好像错了,咱抽嘴),然后咱们考虑插入一个点,首先按横坐标插入,插入的时候要判断合法性(先把插入点splay到根,然后找前驱后继,看这个点是在前驱后继的那一边),然后考虑维护,咱们继续用前驱后继法,咱们给每一个点再记录一个它的前驱和后继是什么,然后咱们对插入的点找前驱后继,再对不合法的情况删除即可(不合法的情况都懂的0.0)。然后咱们就维护这个凸壳,就可以AC这道题。
   每一个点仅插入一次删除一次,然后每个点找前驱后继总共只找O(n)次前驱后继,所以复杂度就是O(nlogn)的。
   然后就是询问 max(a*x[i]+b*y[i]),考虑 P=a*x[i]+b*y[i],即有 y[i]=P/b-a*x[i]/b,咱们要使P最大,实际上失球-a*x/b+C=y这条直线最先碰到的点,也就是 凸壳上 -a/b这个斜率的转折点。然后这个就可以二分了。

   从没写过这个233...写完了才发现要讨论的东西还是比较多的= =
   
   代码略丑,主要是为了思路清晰所以写了的很多东西都是重复的甚至多余的= =

   删除的时候略纠结了一下,然后询问某神犇(大雾)的时候才知道...splay每访问一个点都需要将该点splay到根才能保证复杂度均摊为O(logn)的...以前为什么splay会写挂的原因会不会跟这个有关...(一直访问完扔一边不管的默默路过= =)

   现在来聊一聊这一题的一些坑点:
   1)乃们有考虑到如果插入的时候插入了一个相同的x的点怎么办么?0.0这个要特判...一开始没加这个特判咱是70分,还有一个点TLE成兔斯基,然后加上去了就90分了233。
   2)精度,0.0....最后10分在于 将精度由 10^-5 变成 10^-8就过了233...又一次检查了一下午的代码,然后被精度坑了2333...

   吐槽:为了40分引发的血案。

====================

program bzoj1492;
const maxn=100010;
type node=record
     son:array[0..1]of longint;
     pre,suc,f:longint;
     id:longint;
     end;
     point=record
     x,y:double;
     end;

var t:array[0..maxn]of node;
    n,s,tot:longint;
    root:longint;
    f:array[0..maxn]of double;
    a,b,r:array[0..maxn]of double;
    p:array[0..maxn]of point;

function wh(p:longint):longint;
begin
  if t[t[p].f].son[1]=p then exit(1)
  else exit(0);
end;

procedure rotate(p:longint);
var y,w,ww:longint;
begin
  y:=t[p].f;
  w:=ord(t[y].son[1]=p);
  ww:=ord(t[t[y].f].son[1]=y);
  t[p].f:=t[y].f;
  t[t[y].f].son[ww]:=p;
  t[t[p].son[w xor 1]].f:=y;
  t[y].son[w]:=t[p].son[w xor 1];
  t[p].son[w xor 1]:=y;
  t[y].f:=p;
end;

procedure splay(p,aim:longint);
begin
  while t[p].f<>aim do
   if t[t[p].f].f=aim then rotate(p)
   else begin
     if wh(p) xor wh(t[p].f)=0 then rotate(t[p].f)
                               else rotate(p);
     rotate(p);
   end;
  if aim=0 then root:=p;
end;

function suc(p:longint):longint;
begin
  if t[p].son[1]=0 then exit(0);
  p:=t[p].son[1];
  while t[p].son[0]<>0 do
   p:=t[p].son[0];
  exit(p);
end;

function pre(p:longint):longint;
begin
  if t[p].son[0]=0 then exit(0);
  p:=t[p].son[0];
  while t[p].son[1]<>0 do
   p:=t[p].son[1];
  exit(p);
end;

function det(a,b,c,d:point):double;
begin
  exit((b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x));
end;

procedure delete(p,root:longint);
var su,pr:longint;
begin
  while (t[p].son[0]<>0)or(t[p].son[1]<>0) do
     rotate(t[p].son[ord(t[p].son[1]<>0)]);
  t[t[p].f].son[wh(p)]:=0;
  splay(t[p].f,root);
end;

procedure insert(id:longint);
var q,now,tmp,su,pr:longint;
    flag:boolean;
begin
  if root=0 then
   begin
     inc(tot);
     t[tot].pre:=0;
     t[tot].suc:=0;
     t[tot].id:=id;
     t[tot].son[0]:=0;
     t[tot].son[1]:=0;
     t[tot].f:=0;
     root:=tot;
     exit;
   end;
  q:=root;flag:=false;
  if abs(p[t[q].id].x-p[id].x)<1e-8 then
     if p[t[q].id].y>p[id].y then exit
       else begin t[q].id:=id;flag:=true;end;
  if not flag then
  while t[q].son[ord(p[t[q].id].x+1e-8<p[id].x)]<>0 do
   begin
    if abs(p[t[q].id].x-p[id].x)<1e-8 then
     if p[t[q].id].y>p[id].y then exit
       else begin t[q].id:=id;flag:=true;break;end;
    q:=t[q].son[ord(p[t[q].id].x+1e-8<p[id].x)];
   end;
  if not flag then
  begin
  inc(tot);now:=tot;
  t[now].pre:=0;
  t[now].suc:=0;
  t[now].id:=id;
  t[now].son[0]:=0;
  t[now].son[1]:=0;
  t[now].f:=q;
  tmp:=ord(p[t[q].id].x+1e-8<p[id].x);
  t[q].son[tmp]:=now;
  end
  else now:=q;
  splay(now,0);
  su:=suc(now);
  if su<>0 then splay(su,now);
  pr:=pre(now);
  if pr<>0 then splay(pr,now);
  if (pr<>0)and(su<>0)then
  if det(p[t[pr].id],p[t[su].id],p[t[pr].id],p[id])<1e-8 then
   begin
     t[t[now].son[0]].f:=0;
     if pr<>0 then splay(pr,0);
     if pr<>0 then t[pr].son[1]:=t[now].son[1];
     t[t[now].son[1]].f:=pr;
     exit;
   end;
  if pr<>0 then t[pr].suc:=now;
  if pr<>0 then
  while (t[pr].pre<>0)and(det(p[id],p[t[pr].id],p[t[pr].id],
  p[t[t[pr].pre].id])<1e-8) do
   begin
     delete(pr,now);
     t[t[pr].pre].suc:=now;
     pr:=t[pr].pre;
   end;
  t[now].pre:=pr;
  if su<>0 then t[su].pre:=now;
  if su<>0 then
  while (t[su].suc<>0)and(det(p[t[t[su].suc].id],p[t[su].id],
  p[t[su].id],p[id])<1e-8)do
   begin
     delete(su,now);
     t[t[su].suc].pre:=now;
     su:=t[su].suc;
   end;
  t[now].suc:=su;
end;

function cal(p,q:point):double;
begin
  if p.x=q.x then exit(-1e20);
  exit((q.y-p.y)/(q.x-p.x));
end;

function query(k:double):longint;
var q:longint;
    l,r:double;
begin
  q:=root;
  while q<>0 do
   begin
     if t[q].pre<>0 then l:=cal(p[t[t[q].pre].id],p[t[q].id])
                    else l:=0;
     if t[q].suc<>0 then r:=cal(p[t[q].id],p[t[t[q].suc].id])
                    else r:=-1e10;
     if (l+1e-8>=k)and(k+1e-8>=r) then
      begin
       splay(q,0);
       exit(t[q].id);
      end;
     if (l+1e-8>=k) then if t[q].son[1]<>0 then q:=t[q].son[1]
                                          else break
                   else if t[q].son[0]<>0 then q:=t[q].son[0]
                                          else break;
   end;
  splay(q,0);
  exit(t[q].id);
end;

procedure init;
var i,id:longint;
begin
  read(n,s);
  f[1]:=s;
  for i:=1 to n do
    read(a[i],b[i],r[i]);
  p[1].y:=s/(a[1]*r[1]+b[1]);
  p[1].x:=p[1].y*r[1];
  p[0].x:=0;
  p[0].y:=0;
  tot:=0;
  insert(1);
  for i:=2 to n do
   begin
     id:=query(-a[i]/b[i]);
     f[i]:=p[id].x*a[i]+p[id].y*b[i];
     if f[i]<f[i-1] then f[i]:=f[i-1];
     p[i].y:=f[i]/(a[i]*r[i]+b[i]);
     p[i].x:=p[i].y*r[i];
     insert(i);
   end;
  writeln(f[n]:0:3);
end;

begin
  init;
end.

  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017