[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;
}