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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1076】【SCOI2008】【奖励关】  

2014-03-31 16:23:45|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出一个游戏奖励关收集物品的规则,每一个物品有价值,然后收集某一个物品可能必须先收集一些其他种类的物品各至少一个才能收集,然后问随机抛K次物品(物品种类随机),问假如咱们每一次都是按最优方案去收集物品的期望得分。
    不会做...一般看到期望啊概率啊什么的题目,果断不会想(比如今年的Noip的笔试的那个青蛙2333333...)
    算期望什么的不是一般都考虑DP么?
    首先最暴力的方法自然是枚举所有的可能的扔宝方式,然后再考虑如何取最优。
    话说咱连给出了扔宝方式考虑怎么取最优都不知道......= =
    突然发现忘记看n的大小了233... n<=15.....
 
    首先如果咱脑抽的导致下面的是胡言乱语的话,可以去看这个题解(比大部分题解详细多了)题解 【链接貌似坏了...= =

    首先咱们要知道什么是全期望公式...假设咱们要计算一个很复杂的东西的期望嘛,咱们可以把这个东西分成很多个小的事件,假设咱们知道这些小事件的概率以及其期望,那么这个复杂的东西的期望就是这些小事件的∑期望x概率。 

    然后来看看这道题....算期望一般都是用dp的吧...所以咱们用 f[i][j] 来表示当前抛宝物抛到了第 i个状态为j的期望,然后j就是被取到的宝物的种类的状态,用二进制表示,其中第j位为1表示第j种宝物被取到了。然后这个的怎么算?咱们考虑用上面那个全期望什么的来算。咱们尝试把f[i][j]这个事件分解。首先第一种情况就是 f[i-1][j]+w[k],k为j中表示的已经取的物品,然后它的概率就是 1/n,然后接下来就是 f[i-1][j-1<<(k-1)]这里就是有一个物品是新加进来的。其实咱们可以这样写上面这个方程 f[i][j] ------->f[i+1][j or 1<<(k-1)],这个就是顺推了。
   但是....这个咱们不知道咱们递推过去的那个f[i+1】【j or 1<<(k-1)】正确性....如果是错误的状态自然不能转。这里其实可以写一个特判函数判断某一个状态是否合法,但是这样略麻烦,所以有一种方法就是...倒着推。

   咱们需要证明这样做的正确性....
   首先倒着推的话这个DP的意义就不同了,这个游戏转化成了这样一个游戏,就是假设乃取了某一个物品,那么它有一个对应集合的物品必须要选择,乃必须在接下来的游戏中得到那些物品。这样子的话f[i][j]的j表示的就是在整场游戏中必须选择的物品的种类。然后咱们考虑转移。由上面的全期望公式,f[i][j]实际上可以分类成第i+1次拿到了哪种物品的事件,然后对于在 j里面的物品,它们的决策按照最优策略显然选的是使得这个期望最大的,也就是说max(f[i+1][j](不选),f[i+1][j or 1<<(k-1)]+w[k](选了)),对于不在j里面的物品,显然它们是不能选的,也就是 f[i+1][j],这个是期望,还有概率,概率实际上就是1/N,所以方程就是这样。然后这样的方程为什么可以确保正确性呢?实际上咱们可以发现,如果某一个状态合法的,那么它显然可以推到合法的状态,而对于不合法的状态它不会推。所以f[1][0]就是答案。

   然后就可以AC了。(咱觉得这题直接看代码理解比讲起来更容易懂...)
==================================

program bzoj1076;
const maxk=110;
      maxn=15;
var f:array[0..maxk,0..1 shl maxn-1]of double;
    limit,w:array[0..maxn]of longint;
    t,n:longint;

function max(a,b:double):double;
begin
  if a>b then exit(a) else exit(b);
end;

procedure init;
var i,j,k:longint;
begin
  read(t,n);
  for i:=1 to n do
    begin
      read(w[i]);
      read(j);
      while j<>0 do
       begin
         limit[i]:=limit[i] or (1 shl (j-1));
         read(j);
       end;
    end;
  for i:=t downto 1 do
   for j:=1<<n-1 downto 0 do
    begin
      f[i][j]:=0;
      for k:=1 to n do
        if (limit[k] and j=limit[k]) then
          f[i][j]:=f[i][j]+max(f[i+1][j],f[i+1][j or (1 shl (k-1))]+w[k])/n
        else
          f[i][j]:=f[i][j]+f[i+1][j]/n;
    end;
  write(f[1][0]:0:6);
end;

begin
  init;
end. 

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

历史上的今天

评论

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

页脚

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