[BZOJ 1076][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\)

题目链接

BZOJ 1076

CodeVS 2425

题解

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\)，手玩一下就可以发现问题所在。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}