hdu 4696 反狀態壓縮+動態規劃

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
#define Maxn 210
int A[Maxn];
double p[Maxn];
char str[Maxn];
int Arr[Maxn][25];
double f[Maxn][2];
int n;

void Bit(int x)<SPAN style="WHITE-SPACE: pre">		</SPAN>//將當前位置的數轉化為二進制
{
    int t=0;
    int tt=A[x];
    while(tt){
        Arr[x][t++]=tt&1;
        tt>>=1;
    }
}

void  Solve(int x)
{
    int i,j;
    memset(f,0,sizeof(f));
    if(Arr[0][x]) 
        f[0][1]=1;
    else
        f[0][0]=1;
    for(i=1;i<=n;i++)
    {
        f[i][1]=f[i-1][1]*p[i];<SPAN style="WHITE-SPACE: pre">	</SPAN>//若沒出現，則當前位置01的概率既為上一位置的01的概率
        f[i][0]=f[i-1][0]*p[i];
        if(str[i]=='&'){<SPAN style="WHITE-SPACE: pre">	</SPAN>//根據&,|,^的結果算出當前01的概率
            if(Arr[i][x]){
            f[i][1]+=f[i-1][1]*(1-p[i]);
            f[i][0]+=f[i-1][0]*(1-p[i]);
            }
            else{
            f[i][0]+=f[i-1][1]*(1-p[i]);
            f[i][0]+=f[i-1][0]*(1-p[i]);
            }
        }
        if(str[i]=='|'){
            if(Arr[i][x]){
            f[i][1]+=f[i-1][1]*(1-p[i]);
            f[i][1]+=f[i-1][0]*(1-p[i]);
            }
            else{
            f[i][1]+=f[i-1][1]*(1-p[i]);    
            f[i][0]+=f[i-1][0]*(1-p[i]);
            }
        }
        if(str[i]=='^'){
            if(Arr[i][x]){
            f[i][0]+=f[i-1][1]*(1-p[i]);
            f[i][1]+=f[i-1][0]*(1-p[i]);
            }else{
            f[i][0]+=f[i-1][0]*(1-p[i]);
            f[i][1]+=f[i-1][1]*(1-p[i]);
            }
        }
    }
}
/*因為位運算不影響進位，所以只需要計算最終每一位出現1的概率，求解期望的時候，轉化為10進制即可。
*/
int main()
{
    int i,j,tt=1;
    while(~scanf("%d",&n)){
        memset(Arr,0,sizeof(Arr));
        for(i=0;i<=n;i++)
        {
            scanf("%d",&A[i]);
            Bit(i);
        }
        getchar();
        for(i=1;i<=n;i++)
        {
            str[i]=getchar();
            getchar();
        }    
        for(i=1;i<=n;i++)
            scanf("%lf",&p[i]);
        double ans=0;
        int tmp=1;
        for(i=0;i<20;i++){
            Solve(i);
            ans+=tmp*f[n][1];
            tmp<<=1;
        }
        printf("Case %d:\n",tt++);
        printf("%0.6lf\n",ans);
    }
    return 0;
}