BZOJ1076. [SCOI2008]奖励关（期望dp/状压/逆序）

本文主要是介绍BZOJ1076. [SCOI2008]奖励关（期望dp/状压/逆序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
　　你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，
每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。
宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1次系统都抛出宝物1（
这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。获取第i种宝物将得到Pi
分，但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过
一次，才能吃第i种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，Pi可
以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。假设你
采取最优策略，平均情况你一共能在奖励关得到多少分值？

输入格式
　　第一行为两个正整数k和n，即宝物的数量和种类。以下n行分别描述一种宝物，其中第一个整数代表分值，随
后的整数依次代表该宝物的各个前提宝物（各宝物编号为1到n），以0结尾。

输出格式
　　输出一个实数，保留六位小数，即在最优策略下平均情况的得分。

样例输入
1 2
1 0
2 0
样例输出
1.500000
提示
【数据规模】
1<=k<=100,1<=n<=15，分值为[-10^6,106]内的整数。

题目来源
没有写明来源

思路： 尝试了一下正序没写对，黄学长是逆序推状压dp，感觉还是很像背包的。

定义 dp[i][s]代表到遍历到第i关，状态为s，还能获得价值的平均值。
期望dp一般逆序，正序定义的话，子状态不好找，而且一旦中断不选，后面就不能选了，这个正序也满足不了。

那么转移的方式就是 $d p [i] [s] + = m a x (d p [i] [s], d p [i + 1] [s ∣ t [i]] + v [i])$
而且要有 dp[i][s] /= n。因为一共有n种物品，每种物品出现可能性为1/n。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int p[105],v[200];
int d[200];
double f[105][1 << 16];int main()
{int k,n;scanf("%d%d",&n,&k);//抛出n次，一共k种物品for(int i = 1;i <= 20;i++){p[i] = (1 << (i - 1));}for(int i = 1;i <= k;i++){int t;scanf("%d",&v[i]);while(scanf("%d",&t)){if(t == 0)break;d[i] += p[t];}}for(int num = n;num >= 1;num--){for(int i = 0;i <= p[k + 1] - 1;i++){for(int j = 1;j <= k;j++){if((d[j] & i) == d[j]){f[num][i] += max(f[num + 1][i],f[num + 1][i | p[j]] + v[j]);}else f[num][i] += f[num + 1][i];}f[num][i] = (double)f[num][i] / k;}}printf("%.6f\n",f[1][0]);return 0;
}