HDU 4649 Professor Tian（反狀態壓縮dp，概率）

題目大意
初始有一個數字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: [email protected] *===========================================*/#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的代碼片