題目大意
初始有一個數字A0， 然後給出A1,A2..An共n個數字，這n個數字每個數字分別有一個操作符，&，|，^
且每個數字出現的概率是pi
如果某個數字出現了，那麼就和前面的數字用它的操作符進行位運算。
問最終的期望值是多少？
思路
這題官方題解說是反狀態壓縮，還是第一次做這種題。
知道了怎麼表示狀態這題就覺得不難做了，賽後1A。
題解官方的已經很詳細了，不再累贅：
反狀態壓縮——把數據轉換成20位的01來進行運算
因為只有20位，而且&,|,^都不會進位，那麼一位一位地看，每一位不是0就是1，這樣求出每一位是1的概率，再乘以該位的十進制數，累加，就得到了總體的期望。
對於每一位，狀態轉移方程如下：
f[i][j]表示該位取前i個數，運算得到j(0或1)的概率是多少。
f[i][1]=f[i-1][1]*p[i]+根據不同運算符和第i位的值運算得到1的概率。
f[i][0]同理。
初始狀態：f[0][0~1]=0或1（根據第一個數的該位來設置）
每一位為1的期望 f[n][1]
代碼
/**========================================== *
This is a solution for ACM/ICPC problem *
* @source: HDU 4649 Professor Tian *
@type: dp * @author: shuangde * @blog: blog.csdn.net/shuangde800 *
@email: zengshuangde@gmail.com *===========================================*/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<map>using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 210;int n, m;double f[MAXN][2];int A[MAXN];char O[MAXN];double p[MAXN];int main(){ char op[10]; int cas = 1; while(~scanf("%d", &n)){
for(int i=0; i<=n; ++i)
scanf("%d", &A[i]);
for(int i=1; i<=n; ++i){
scanf("%s", op);
O[i] = op[0];
} for(int i=1; i<=n; ++i)
scanf("%lf", &p[i]);
for(int i=0; i<20; ++i) f[0][0] = (A[i]>>i)&1;
double ans = 0;
for(int i=0; i<20; ++i){ f[0][1] = (A[0]>>i)&1;
f[0][0] = !f[0][1];
for(int j=1; j<=n; ++j){
// 第j個數字不出現，0和1的概率 f[j][0] = f[j-1][0] * p[j];
f[j][1] = f[j-1][1] * p[j];
// 加上出現第j個數字，0和1的概率 if(O[j] == '^'){
if( (A[j]>>i) & 1 ){ f[j][0] += f[j-1][1]*(1-p[j]);
f[j][1] += f[j-1][0]*(1-p[j]);
} else{ f[j][0] += f[j-1][0]*(1-p[j]);
f[j][1] += f[j-1][1]*(1-p[j]);
} } else if(O[j] == '&'){ if( (A[j]>>i) & 1 ){
f[j][0] += f[j-1][0]*(1-p[j]);
f[j][1] += f[j-1][1]*(1-p[j]);
} else{ f[j][0] += (f[j-1][0] + f[j-1][1]) * (1-p[j]);
// f[j][1]: 如果用了第j個數，這裡不能出現1
} } else if(O[j] == '|'){ if( (A[j]>>i) & 1){
// f[j][0]: 不能出現這種情況
f[j][1] += (f[j-1][0] + f[j-1][1]) * (1-p[j]); } else{
f[j][0] += f[j-1][0] * (1-p[j]);
f[j][1] += f[j-1][1] * (1-p[j]);
} } } ans = ans + f[n][1] * (1<<i);
} printf("Case %d:\n%.6f\n", cas++, ans); } return 0;}
來自CODE的代碼片
