自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:38:06，当前版本为作者最后更新于2017-08-18 12:04:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很明显是一道状压。$DP$模型很容易想到，用$f[i][S]$表示到了第$i$轮，宝物是否取过的状态为$S$的最大期望得分。

但这个模型存在问题：可能在第$i$轮无法到达状态$S$。

所以，这里把定义换一下，$f[i][S]$表示在第$1$轮到第$i-1$轮内宝物是否取过的状态为$S$，第$i$轮到第$K$轮的最大期望得分，那么这样就可以通过逆推进行转移了。

转移方程为：

对于任意一个$1<=k<=n$，

1、如果$S$包含的状态满足取第$k$种宝物的条件，则可以取或不取。不取则为$f[i+1][S]$，取则为$f[i+1][S|(1<<k-1)]+P_k$。

所以此时$f[i][S]+=max(f[i+1][S],f[i+1][S|(1<<k-1)]+P_k)$。

2、如果$S$包含的状态不满足取第$k$种宝物的条件，则不能取，即$f[i][S]+=f[i+1][S]$。

而这里求的是期望值，上面求的东西覆盖了第$i$轮取了所有$n$种宝物的情况，所以在每一个状态计算完之后，把$f[i][S]$除以$n$即为期望平均值。

最后答案为$f[1][0]$。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int M = 105, N = 17;
int K, n, p[N], sta[N];
double f[M][1 << 15];
void chkmax(double &a, double b) {a = max(a, b);}
int main() {
    int i, j, k, x; K = read(); n = read();
    for (i = 1; i <= n; i++) {
        p[i] = read(); while (x = read())
            sta[i] = sta[i] | (1 << x - 1);
    }
    for (i = K; i >= 1; i--) for (j = 0; j < (1 << n); j++) {
        for (k = 1; k <= n; k++) if ((j & sta[k]) == sta[k])
            f[i][j] += max(f[i + 1][j], f[i + 1][j | (1 << k - 1)] + p[k]);
        else f[i][j] += f[i + 1][j];
        f[i][j] /= n;
    }
    printf("%.6lf\n", f[1][0]);
    return 0;
}