题目大意
有 n 个物品,每个物品有一个价值 wi,有些物品在吃之前要先吃过一些其他的物品。给定 k 次,每次可以选择吃一个物品或不吃,若选择吃,每种物品会等概率被吃到。求最优策略下的期望得分。
1⩽n⩽15
1⩽k⩽100
−1,000,000⩽wi⩽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,手玩一下就可以发现问题所在。
代码
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; }
|