https://www.luogu.org/problem/P2473
看数据范围, 不是搜索就是状压
于是就开心状压, 先不要管他什么期望
DP 模型很容易想到,
用 f[i,S] 表示到了第 i 轮, 宝物是否取过的状态为 S 的最大期望得分.
但这个模型存在问题: 可能在第 i 轮无法到达状态 S 为什么呢?
比如你枚举 i 的时候是从 1 开始的, 而此时你又要枚举 j 从 0 到 1<<(n-1),
肯定是不行的啊, 那怎么办?
所以, 这里把定义换一下
f[i,S] 表示在第 1 轮到第 i-1 轮内宝物是否取过的状态为 S, 第 i 轮到第 K 轮的最大期望得分,
那么这样就可以通过逆推进行转移了.
转移方程为:
对于任意一个 1<=k<=n
1, 如果 S 包含的状态满足取第 k 种宝物的条件, 则可以取或不取. 不取则为 f[i+1,S], 综合取则为 max(f[i+1,S],f[i+1,S|(1<<k-1)]+val[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;
- }
来源: http://www.bubuko.com/infodetail-3231421.html