hdu - 4649 - Professor Tian（概率dp）

题意：一个数学表达式，n+1个操作数，n个操作符（&, |, ^），每个操作符及其后面的那个操作数有一个消失的概率，问表达式的期望（操作数 < 2^20, 0 < n <= 200）。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4649

——>>操作数的范围 < 2^20，在暗示着此题用位运算——每个操作数可化为最多20位的二进制数，求出n+1个数的运算后每一个二进制位出现1的概率（出现0的概率不用求，若这一位是0，那么总数的大小与这一位无关，只是占位作用）。

设a[i][j]表示第i个数的第j个二进制位；p[i][j]表示对于二进制位的第bit位，前i个数运算后得到j的概率（j为0或1）；d[i]表示这n+1个数运算后第i个二进制位出现1的概率。

对于p[i][j]，状态转移方程如下：

p[i][1] = p[i-1][1] * P[i] + 各种运算产生的概率。

p[i][0] = 1 - p[i][1]。

#include <cstdio>using namespace std;const int maxn = 200 + 3;
const int maxm = 20 + 3;
int A[maxn], a[maxn][maxm], n;
char O[maxn];
double P[maxn], p[maxn][2], d[maxm];void read(){int i;for(i = 0; i < n+1; i++) scanf("%d", &A[i]);for(i = 1; i <= n; i++){getchar();O[i] = getchar();}for(i = 1; i <= n; i++) scanf("%lf", &P[i]);
}void init(){int i, j;for(i = 0; i < n+1; i++)for(j = 0; j < 20; j++) a[i][j] = (1 << j) & A[i];
}void dp(){int i, bit;for(bit = 0; bit < 20; bit++){if(a[0][bit]){p[0][1] = 1;p[0][0] = 0;}else{p[0][0] = 1;p[0][1] = 0;}for(i = 1; i < n+1; i++){p[i][1] = p[i-1][1] * P[i];switch(O[i]){case '&':{if(a[i][bit]) p[i][1] += p[i-1][1] * (1 - P[i]);break;}case '|':{if(a[i][bit]) p[i][1] += 1 - P[i];else p[i][1] += p[i-1][1] * (1 - P[i]);break;}case '^':{if(a[i][bit]) p[i][1] += p[i-1][0] * (1 - P[i]);else p[i][1] += p[i-1][1] * (1 - P[i]);break;}}p[i][0] = 1 - p[i][1];}d[bit] = p[n][1];}
}double solve(){double ret = 0;for(int i = 0; i < 20; i++) ret += (1 << i) * d[i];return ret;
}int main()
{int kase = 1;while(scanf("%d", &n) == 1){read();init();dp();printf("Case %d:\n%.6lf\n", kase++, solve());}return 0;
}