洛谷P2473 [SCOI2008] 奖励关题解

题目链接：P2473 [SCOI2008] 奖励关

题意：

你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。

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

获取第 $i$ 种宝物将得到 $p_i$ 分，但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $s_i$。只有当 $s_i$ 中所有宝物都至少吃过一次，才能吃第 $i$ 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，$p_i$ 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。

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

输入格式：

第一行为两个整数，分别表示抛出宝物的次数 $k$ 和宝物的种类数 $n$。

第 $2$ 到第 $(n + 1)$ 行，第 $(i + 1)$ 有若干个整数表示第 $i$ 个宝物的信息。每行首先有一个整数，表示第 $i$ 个宝物的分数 $p_i$。接下来若干个互不相同的整数，表示该宝物的各个前提宝物集合 $s_i$，每行的结尾是一个整数 $0$，表示该行结束。

输出格式：

输出一行一个实数表示答案，保留六位小数。

数据范围：

对于全部的测试点，保证 $1 \leq k \leq 100$，$1 \leq n \leq 15$，$-10^6 \leq p_i \leq 10^6$。

显然考虑状压dp。这里记 $P_i$ 为分数，$S_i$ 为 $i$ 的前置集合。

如果设 $f(i,\mathcal{S})$ 表示当前吃过集合 $\mathcal{S}$ 的物品时（仅前 $i$ 个物品），前 $i$ 个物品的最优期望得分。

那么在转移的时候，并不确定 $i$ 之前有没有吃过，于是根本没法转移。

重新设 $f(i,\mathcal{S})$ 表示当前吃过集合 $\mathcal{S}$ 的物品时（仅前 $i$ 个物品），后 $i-k$ 个物品的最优期望得分。

考虑转移（显然需要倒着转移），枚举下一个随机的宝物是 $j$ 。

如果 $S_j\subseteq \mathcal{S}$ ，那么就直接吃了，有
$f(i,\mathcal{S}) \operatorname{\big\uparrow} \frac{1}{n} \max \left\{f(i+1, \mathcal{S}),\ f(i+1, \mathcal{S} \cup\{j\})+P_j\right\}$
如果 $S_j\not\subseteq \mathcal{S}$ ，那么就不能吃，于是
$f(i,\mathcal{S}) \operatorname{\big\uparrow} \frac{1}{n} f(i + 1,\mathcal{S})$

上面式子里 $a\uparrow b$ 表示增量 $a \gets a + b$ 。最后答案就是 $f(0,\varnothing)$ 。

时间复杂度 $\mathcal{O}(nk2^n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void up(double &x, double y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N 16
#define K 136

int P[N], S[N]; double inv, f[K][(1 << 16) + 15];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> m >> n;
    rep(i, 0, n - 1)
    {
        cin >> P[i];
        for(int t; cin >> t && t; S[i] |= 1 << (--t));
    }
    int mx = (1 << n) - 1; inv = 1.0 / n;
    Rep(i, m - 1, 0) rep(j, 0, mx)
    {
        rep(k, 0, n - 1)
        {
            const double t = ((~j) & S[k]) ? 0 : f[i + 1][j | (1 << k)] + P[k];
            f[i][j] += max(f[i + 1][j], t);
        }
        f[i][j] *= inv;
    }
    cout << fixed << setprecision(6) << f[0][0] << '\n';
    return 0;
}