BZOJ 1076 奖励关 状态压缩DP

题目链接：

https://www.lydsy.com/JudgeOnline/problem.php?id=1076

题目大意：

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

思路：
这一步的期望=(上一步的期望+这一步的得分)/K

逆向推

 #include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf

 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Mem(a) memset(a, 0, sizeof(a))

 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))

 #define MID(l, r) ((l) + ((r) - (l)) / 2)

 #define lson ((o)<<1)

 #define rson ((o)<<1|1)

 #define Accepted 0

 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 typedef long long ll;

 const int maxn = ;

 const int MOD = ;//const引用更快，宏定义也更快

 const int INF = 1e9 + ;

 const double eps = 1e-;

 const double pi = acos(-);

 double v[];

 int d[];

 double dp[][];

 int main()

 {

     int k, n, x;

     cin >> k >> n;

     for(int i = ; i <= n; i++)

     {

         cin >> v[i];

         while(cin >> x && x)d[i] += ( << (x - ));

     }

     for(int i = k; i >= ; i--)

     {

         for(int j = ; j < ( << n); j++)

         {

             for(int c = ; c <= n; c++)

                 if((d[c] & j) == d[c])//j状态包含了c的所有前驱物品

                     dp[i][j] += max(dp[i + ][j], dp[i + ][j | (<<(c - ))] + v[c]);//第i次啥都不取，或者取第c件物品

                 else dp[i][j] += dp[i + ][j];

             dp[i][j] /= n;

         }

     }

     printf("%.6f\n", dp[][]);

     return Accepted;

 }