题目描述
你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 (k) 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。
宝物一共有 (n) 种，系统每次抛出这 (n) 种宝物的概率都相同且相互独立。也就是说，即使前 (left(k-1
ight)) 次系统都抛出宝物 (1)（这种情况是有可能出现的，尽管概率非常小），第 (k) 次抛出各个宝物的概率依然均为 (frac{1}{n})。
获取第 (i) 种宝物将得到 (p_i) 分，但并不是每种宝物都是可以随意获取的。第 (i) 种宝物有一个前提宝物集合 (s_i) 。只有当 (s_i) 中所有宝物都至少吃过一次，才能吃第 (i) 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会。注意，(p_i) 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。
假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？
输入格式
第一行为两个整数，分别表示抛出宝物的次数 (k) 和宝物的种类数 (n)。
第 (2) 到第 (left(n + 1
ight)) 行，第 (left(i + 1
ight)) 有若干个整数表示第 (i) 个宝物的信息。每行首先有一个整数，表示第 (i) 个宝物的分数 (p_i)。接下来若干个互不相同的整数，表示该宝物的各个前提宝物集合 (s_i)，每行的结尾是一个整数 (0)，表示该行结束。
输出格式
输出一行一个实数表示答案，保留六位小数。
首先枚举状态我们需要考虑状压, 设计状态为f[k][S], 表示在第 (k) 秒, 选择宝物的状态为 (S).
然后发现正序是无法 DP 的, 因为每种状态的转移会受到前一种状态的影响 (每种宝物的选择会受到前置宝物的影响),
于是考虑倒序, 从 f[k+1][S] 向前转移.
转移方程:
代码:
# include <iostream>
# include <cstdio>
# define MAXK 105
# define MAXN 15
using namespace std;
int k, n;
int p[MAXK];
int pre[MAXK]; // pre 记录每个点的前置点
double f[MAXK][1<<MAXN];
int main(){
int tmp;
scanf("%d%d", &k, &n);
for(int i = 1; i <= n; i++){
scanf("%d", &p[i]);
int tmpS = 0;
scanf("%d", &tmp);
while(tmp != 0){
tmpS |= 1<<(tmp-1);
scanf("%d", &tmp);
}
pre[i] = tmpS;
}
for(int i = k; i >= 1; i--) // 枚举时间
for(int j = 0; j < (1<<n); j++){ // 枚举当前状态
for(int t = 1; t <= n; t++){ // 枚举宝物
if((j&pre[t]) == pre[t]) // 可以取
f[i][j] += max(f[i+1][j], f[i+1][j|1<<(t-1)]+1.0*p[t]);
else
f[i][j] += f[i+1][j];
}
f[i][j] /= 1.0*n; // 每种状态有 1/n 的概率被选择
}
printf("%.6lf", f[1][0]);
return 0;
}