Description
你正在玩你最喜欢的电子游戏, 并且刚刚进入一个奖励关在这个奖励关里, 系统将依次随机抛出 k 次宝物,
每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择, 且现在决定不吃的宝物以后也不能再吃)
宝物一共有 n 种, 系统每次抛出这 n 种宝物的概率都相同且相互独立也就是说, 即使前 k-1 次系统都抛出宝物 1(
这种情况是有可能出现的, 尽管概率非常小), 第 k 次抛出各个宝物的概率依然均为 1/n 获取第 i 种宝物将得到 Pi
分, 但并不是每种宝物都是可以随意获取的第 i 种宝物有一个前提宝物集合 Si 只有当 Si 中所有宝物都至少吃过
一次, 才能吃第 i 种宝物 (如果系统抛出了一个目前不能吃的宝物, 相当于白白的损失了一次机会) 注意, Pi 可
以是负数, 但如果它是很多高分宝物的前提, 损失短期利益而吃掉这个负分宝物将获得更大的长期利益 假设你
采取最优策略, 平均情况你一共能在奖励关得到多少分值?
Input
第一行为两个正整数 k 和 n, 即宝物的数量和种类以下 n 行分别描述一种宝物, 其中第一个整数代表分值, 随
后的整数依次代表该宝物的各个前提宝物(各宝物编号为 1 到 n), 以 0 结尾
Output
输出一个实数, 保留六位小数, 即在最优策略下平均情况的得分
- Sample Input
- 1 2
- 1 0
- 2 0
- Sample Output
- 1.500000
- HINT
数据规模
1<=k<=100,1<=n<=15, 分值为 [-10^6,10^6] 内的整数
f[i][j]表示当前该拿第 i 个了, 拿之前状态为 j
第一道概率 DPemmm 俗话说顺推概率, 逆推期望
总结里有相关说明
这个题我们预处理一下前提集合,
然后转移的时候判断当前状态是否包含前提集合再进行转移即可
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- int N,K,v[20],pre[20],x;
- double f[105][40001];
- using namespace std;
- int main()
- {
- scanf("%d%d",&N,&K);
- double p=1.0/K;
- for (int i=1;i<=K;++i)
- {
- scanf("%d%d",&v[i],&x);
- while (x)
- pre[i]|=(1<<x-1),scanf("%d",&x);//pre 记录前提宝物
- }
- for (int i=N;i>=1;--i)
- for (int j=0;j<=(1<<K)-1;++j)
- for (int k=1;k<=K;++k)
- if ((pre[k]&j)==pre[k])
- f[i][j]+=p*max(f[i+1][j],f[i+1][j|(1<<k-1)]+v[k]);
- else
- f[i][j]+=p*f[i+1][j];
- printf("%0.6lf",f[1][0]);
- }
1076. [SCOI2008]奖励关状压 DP + 期望
来源: http://www.bubuko.com/infodetail-2544898.html