[学习笔记]2018/2/26

oi
  1. 1. 概率期望dp与状压dp
    1. 1.1. 概率期望dp
    2. 1.2. 状压dp+概率期望

概率期望dp与状压dp


$P(A)$ A -> 发生的概率
$E(a)$ -> 发生这件事的期望
$P(A) = \frac{1}{E(A)}$
发生这件事的期望是概率的倒数
通俗来说,就是买N次能够买到(非洲人除外

概率期望dp

k: k + 1
k种物品的期望次数是$\frac{n-k}{n}$
买第一个的概率是1,期望是$\frac{1}{1}$
买第二个的概率是$\frac{2}{3}$,期望是$\frac{3}{2}$
所以总期望是$\sum_{i=1}^n{(\frac{n}{i})}$

买了k个,k + 1
f[k]已经有了k种,还需要购买的次数
$f[k] = f[k + 1] + \frac{n}{n-k}$
$g[k]$集齐了k种,到了n种需要花费的钱
$g[k] = \frac{n-k}{n}(g[k + 1] + f[k + 1])+\frac{k}{n}(g[k]+f[k]) + 1$
$g[k] = g[k + 1] + f[k + 1]\times\frac{k}{n-k}\times f[k]+\frac{n}{n-k}$

状压dp+概率期望

对着题解盯了半天

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
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

inline int read()
{
char c = getchar();
int ret = 0, f = 1;
for (; !isdigit(c); f = c == '-' ? -1 : 1, c = getchar());
for (; isdigit(c); ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

const int maxk = 105, maxn = 20;
int f[maxk][1 << 15];
int k, n, p[n], val, req[n];

int main()
{
k = read(); n = read();
for (int i = 1; i <= n; ++i)
{
read(p[i]);
while(val = read())
req[i] = (req[i] | 1 << val - 1);
} // init the value of a and required

for (int i = k; i >= 0; --i)
// enumerate status of binary
for (int j = 0; j < (1 << n); ++j)
for (int qwq = 1; qwq <= n; ++qwq)
{
if((j & req[qwq]) == req[qwq])
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("%.6f", f[1][0]);
}

题面
按照题解的话来说,这道题的状态有点特殊
从$[1..i - 1]$的取过的状态为S,表示从$[i..k]$的期望最大值。
可以得到这个:
如果满足到当前的条件
则可以选当前、不选
$f[i][j] += \mathrm{max}(f[i+1][j],f[i+1][j\;|\;(1<<k)]+p[k])$
刚才给过定义,表示从$[1..i-1]$的状态是s,选取了一个,所以$f[i+1][j\;|\;(1<<k)]$的状态表示“[1..i]的状态是选取了下一个的”
如果不能达到当前的条件,只能不选
$f[i][j] += f[i+1][j]$
END