SCOI2008 奖励关

题意

在奖励关里,系统将依次随机抛出 k 次宝物,每次你都可以选择吃或者不吃。宝物一共有 n 种,第 k 次抛出各个宝物的概率均为

获取第 i 种宝物将得到 分( 可以是负数),但第 i 种宝物有一个前提宝物集合 。只有当 Si 中所有宝物都至少吃过一次,才能吃第 i 种宝物,如果系统抛出了一个目前不能吃的宝物,相当于损失一次机会

假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?

.

分析

定义 表示第 轮吃过的状态为 ,第 轮的期望平均得分

那么采用倒推的方式,我们考虑 转移:

  1. 如果 的前提宝物都被吃过:

    1. 那么就能吃 .
    2. 选择不吃: .
  2. 否则就不能吃 ,期望为 .

这里的关系是等价的,也就是说, 是否能吃是固定的,那么 1,2 是相互独立的,概率各自为 1/0.

而吃或不吃是没有概率之分的,那么 1.1 和 1.2 是独立的,选取最大值.

也就是说,对于一个宝物只会在三者中选择一个来贡献

贡献完之后再除以 n 就是平均值.

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=15,K=102;
int k,n;
int p[N],s[N];
double f[K][1<<N];

int main(){scanf("%d%d",&k,&n);
    for(int i=1,x;i<=n;i++){scanf("%d",&p[i]);
        while(~scanf("%d",&x)&&x)s[i]|=1<<x-1;}
    int mxj=1<<n;
    for(int i=k;i>=1;i--){for(int j=0;j<mxj;j++){for(int a=1;a<=n;a++){if((j|s[a])==j)f[i][j]+=max(f[i+1][j],f[i+1][j|1<<(a-1)]+p[a]);
                else f[i][j]+=f[i+1][j];
            }
            f[i][j]/=n;
        }
    }
    printf("%lf",f[1][0]);
    return 0;
}

  转载请注明: Sshwy's Blog SCOI2008 奖励关

 上一篇
[HAOI2012] 高速公路 [HAOI2012] 高速公路
题意Y901 高速公路是一条由 段路以及 个收费站组成的东西向的链,收费站依次编号为 ,从收费站 行驶到 (或从 行驶到 ) 需要收取一定的费用,高速路刚建成时所有的
2019.01.17
下一篇 
[SCOI2010] 股票交易 [SCOI2010] 股票交易
题意对于一个股市,给出第 天买 / 卖股票的价格和买 / 卖股票的数量,依次为 . 并要求手上的股票数不超过 ,两次交易的间隔时间至少 天(买卖都各算一次交易),初始时有
2019.01.16
  目录