[SCOI 2008] 奖励关

题目大意

有 $n$ 个物品，每个物品有一个价值 $w_i$，有些物品在吃之前要先吃过一些其他的物品。给定 $k$ 次，每次可以选择吃一个物品或不吃，若选择吃，每种物品会等概率被吃到。求最优策略下的期望得分。

$1 \leqslant n \leqslant 15$

$1 \leqslant k \leqslant 100$

$-1,000,000 \leqslant w_i \leqslant 1,000,000$

题目链接

【SCOI 2008】奖励关 - Luogu 2473

题解

DP + 状态压缩。

记 $f[i,\; s]$ 为考虑到第 $i$ 次，状态为 $s$ 时的答案。由于一般的正序递推可能会推到不合法的状态上，故我们倒序递推，保证一定从合法的状态转移来。

f[i, \; s] \rightarrow \begin{cases} \begin{align} f[i + 1, \; s] &\\ f[i +1, \; s \; | \; j] + w_j &\quad j \ 是可选的物品 \end{align} \end{cases}

把后面那一堆加起来，再除以 $n$ 就是第 $i$ 天的期望。

再详细说一下正推的问题（本人想了一个小时。。。）：无论是正推还是倒推，我们都只考虑了当前这一步是否合法，但可能原来的状态就是不合法的（比如当前考虑某物品是否可被吃，而它的需求集合里，有的物品仍然有其非空的需求集合）。倒推时，我们把物品逐一减少，最后的答案就是 $f[1, \; 0]$，而正推时我们一个个地添加物品，答案是 $f[k, \; s]$，$s$ 还要再枚举一遍。不过，这不是问题所在。正推与倒推只是方向相反的问题，而问题出在只有一个东西时，正推虽然不会让 $f[i, \; 0]$ 向 $f[i + 1, \; 0 \; | \; j]$（$j$ 有非空需求集合的）转移，但后者的值显然还是 $0$，意思是之后的情况下，它仍会像视一个合法方案一样去更新其他的值；倒推时，$f[1, \; 0]$ 就是答案，答案只会从合法的只有一个东西的状态转移来，就算那些不合法的值是 $0$，但转移时不会从那里转移，就不会有问题。

可以考虑这样的栗子：东西为 $\{a, \; b, \; c\}$，其中 $b$ 需要 $a$，$c$ 需要 $b$，手玩一下就可以发现问题所在。

代码

#include <cstdio>
#include <algorithm>
const int MAXN = 20;
const int MAXSTATUE = 65536;
const int MAXK = 105;
double f[MAXK][MAXSTATUE];
int need[MAXN], w[MAXN], pow[MAXN];
int k, n;
void dp() {
    for (int i = k; i; i--) for (int s = 0; s < pow[n + 1]; s++) {
        for (int j = 1; j <= n; j++) {
            if (need[j] == (need[j] & s)) f[i][s] += std::max(f[i + 1][s], f[i + 1][s | pow[j]] + w[j]);
            else f[i][s] += f[i + 1][s];
        }
        f[i][s] /= n;
    }
}
int main() {
    scanf("%d %d", &k, &n);
    for (int i = 1; i <= n + 1; i++) pow[i] = 1 << (i - 1);
    for (int i = 1; i <= n; i++) {
        int t;
        scanf("%d %d", &w[i], &t);
        while (t) {
            need[i] += pow[t];
            scanf("%d", &t);
        }
    }
    dp();
    printf("%.6lf\n", f[1][0]);
    return 0;
}