hdu 4649 Professor Tian

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【重做DP系列】 概率(期望)DP,状态压缩DP

【2013多校联合训练第五场】

题意:有3种位运算,&,|,^,有n+1个数字,n个运算符,其中第1个数字必定存在。运算符可能有p的概率会消失,那么运算符后面紧接的那个数字就不能被计算。最后能这个算式结果的数字期望值是多少。

留意到到一点,每个数字都 < 2^20,也就是说写成二进制就20位。另外位运算是按位操作的,一个位上的变化不会影响其他位。我们不妨把所有数字都变为一个20位长度的二进制数,然后用它来计算。要算最后式子结果的期望值,只需要知道这20位中每一位为1的概率是多少

设dp[n][id],在进行完第n个运算符后,20位二进制中的第id位为1的概率

那么最后的结果为

res = dp[n][0](2^0) + dp[n][1](2^1) + dp[n][2](2^2) + ……… + dp[n][19] (2^19)

现在我们来看看怎么转移,需要分类讨论

&运算:

若第n个数字,第id位为1,它不消失的时候: dp[n][id] = (1-p) dp[n-1][id]; 消失的时候直接继承上次的1:dp[n][id] = p dp[n-1][id];

因此第id位为1时:dp[n][id] = dp[n-1][id]

第id位为0,若它不消失,第id肯定为0,只有消失,才能继承上一次的1

dp[n][id] = p * dp[n-1][id];

|运算:

若第id位为1,若它不消失,则第id位一定为1:dp[n][id] = 1-p; 若它消失,只有继承上一次的才能为1:dp[n][id] = p * dp[n-1][id];

因此第id位为1时:dp[n][id] = 1-p + p * dp[n-1][id];

若第id为0,若它不消失,则上一次一定要为1:dp[n][id] = (1-p) * dp[n-1][id];

^运算:

若第id位为1,若它不消失,那上一次一定要为0:dp[n][id] = (1-p) (1-dp[n-1][id]);若它消失,则继承上一次的: dp[n][id] = p dp[n-1][id];

因此第id位为1时:dp[n][id] = (1-p) (1-dp[n-1][id]) + p dp[n-1][id];

若第id位为0,若它不消失,那上一次一定要为1: dp[n][id] = (1-p) dp[n-1][id]; 若它消失,则继承上一次的: dp[n][id] = p dp[n-1][id];

因此第id位为0时:dp[n][id] = (1-p) dp[n-1][id] + p dp[n-1][id];

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 210
#define M 25
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

double dp[N][M],p[N];
int n,num[N];
char op[N][5];

int main(){
int cas = 0;
while(scanf("%d",&n)!=EOF){
for(int i = 0; i <= n; i++)
scanf("%d",&num[i]);
for(int i = 1; i <= n; i++)
scanf("%s",op[i]);
for(int i = 1; i <= n; i++)
scanf("%lf",&p[i]);

for(int i = 0; i <= n; i++)
for(int j = 0; j <= 20; j++)
dp[i][j] = 0.0;
int bit[M];
cl(bit,0);
for(int i = 0; i < 20; i++){
bit[i] = num[0]&1;
dp[0][i] = (bit[i] == 1 ? 1.0 : 0.0);
num[0] >>= 1;
}
for(int i = 1; i <= n; i++){
cl(bit,0);
for(int id = 0; id < 20; id++){
bit[id] = num[i]&1;
num[i] >>= 1;
if(op[i][0] == '&'){
if(bit[id] == 1) dp[i][id] = dp[i-1][id];
else dp[i][id] = dp[i-1][id] * p[i];
}
else if(op[i][0] == '|'){
if(bit[id] == 1) dp[i][id] = p[i] * dp[i-1][id] + (1-p[i]);
else dp[i][id] = dp[i-1][id];
}
else{
if(bit[id] == 1) dp[i][id] = p[i] * dp[i-1][id] + (1-p[i]) * (1-dp[i-1][id]);
else dp[i][id] = p[i] * dp[i-1][id] + (1-p[i]) * dp[i-1][id];
}
}
}
double ans = 0;
for(int i = 0; i < 20; i++){
ans += ((double)(1<<i) * dp[n][i]);
}
printf("Case %d:\n",++cas);
printf("%.6lf\n",ans);
}
return 0;
}