在这个奖励关里，系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃 (必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃)。

宝物一共有 $n$ 种，系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。也就是说，即使前 $k-1$ 次系统都抛出宝物 $1$ (这种情况是有可能出现的，尽管概率非常小)，第 $k$ 次抛出各个宝物的概率依然均为 $\dfrac 1n$。

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

注意，$P_i$ 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。

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

输入格式

第一行包含两个正整数 $k, n$ ($k \leq 100, n \leq 15$)，表示宝物的数量和种类。

接下来的 $m$ 行，分别描述 $m$ 种宝物，其中每行包含两个整数，其中第一个整数 $P_i$ ($|P_i| \leq 10^6$) 代表分值，随后的整数依次代表该宝物的各个前提宝物 (各宝物编号为 $1$ 到 $n$)，以 $0$ 结尾。

输出格式

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

题解

对于第 $i$ 种宝物，如果 $S_i$ 中的宝物全部噎过，那么你才能噎第 $i$ 种宝物。

记状态 $(i, S)$ 表示前 $i$ 个宝物中，噎过的宝物组成了集合 $S$。那么 $f_{i, S}$ 表示什么呢？如果 $f_{i, S}$ 表示这样前 $i$ 个宝物 (在最优情况下) 的得分期望，那么转移的时候，$1 \sim i-1$ 个宝物中，噎过的宝物组成的集合是 $S$，还是 $S$ 减去某个元素，这不好清楚。

于是换一种思路，记 $f_{i, S}$ 表示前 $i$ 个宝物中，噎过的宝物组成的集合是 $S$，那么后面 $k - i$ 种宝物 (在最优情况下) 的得分期望。那么必须倒着转移，这样对于给定的 $(i, S)$，再噎一个宝物，所得的新的 $(i', S')$ 也是可以轻松得到的。

考虑转移，随机下一个宝物是 $j$，如果 $S_j \subseteq S$，那么就可以噎它了，此时宝物 $j$ 对应的贡献即为 $$ \Large \frac 1n \max \left\{ f_{i+1, S}, f_{i+1, S \cup \{j\}} + P_j \right\} $$

如果 $S_j \nsubseteq S$，那么就不能噎它，此时宝物 $j$ 对应的贡献即为 $$ \Large \frac 1n f_{i+1, S} $$

最后将所有 $j$ 对应的贡献加起来，就得到了 $f_{i, j}$，最后 $f_{0, \varnothing}$ 就是答案，时间复杂度为 $O(2^n nk)$。

代码

#include <bits/stdc++.h>
#define N 17
#define N2 85367
#define K 136
using namespace std;

int n, m, t;
int i, j, k;
int P[N], S[N];
double f[K][N2], r, n1;

inline void up(double &x, const double y) {x < y ? x = y : 0;}

int main(){
    scanf("%d%d", &m, &n);
    for(i = 0; i < n; ++i)
        for(scanf("%d", P + i); scanf("%d", &t) == 1 && t; S[i] |= 1 << --t);
    t = 1 << n; n1 = 1.0 / (double)n;
    for(i = m - 1; i >= 0; --i)
        for(j = 0; j < t; ++j){
            for(k = 0; k < n; ++k){
                r = f[i + 1][j];
                if(!(~j & S[k]))
                    up(r, f[i + 1][j | 1 << k] + (double)P[k]);
                f[i][j] += r;
            }
            f[i][j] *= n1;
        }
    printf("%lf\n", f[0][0]);
    return 0;
}

坑

由于后面一维操作只和集合 $S$ 和宝物 $j$，因此 DP 时第一维 $i$ 可以滚动掉 ~~(只是我懒得滚动罢了)~~。

题目描述

输入格式

输出格式

题解

代码

坑