思路：每个数取他的二进制位，对于每一位，我们求他最后出现1的概率，那么最后的期望就是为1的概率乘以该位的十进制数，累加即可。
想到状压就是水题…
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos（-1.0）
#define Max 2505
#define inf 0x7fffffff
#define LL（x） （ x 《 1 ）
#define RR（x） （ x 《 1 | 1 ）
#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
#define ll long long
#define mem（a,b） memset（a,b,sizeof（a））
#define mp（a,b） make_pair（a,b）
#define PII pair<int,int>
#define bug puts（"here"）
using namespace std;
#define N 222
double dp[22][N] ;//第i位第j个数是k的概率。
int a[N] ;
char b[N] ;
double p[N] ;
int n ;
int main（） {
int ca = 0 ;
while（cin 》 n）{
for （int i = 0 ; i <= n ; i ++ ）{
scanf（"%d",&a[i]） ;
}
for （int i = 1 ; i <= n ; i ++ ）{
cin 》 b[i] ;
}
for （int i = 1 ; i <= n ; i ++ ）{
cin 》 p[i] ;
}
for （int i = 0 ; i <= n ; i ++ ）{
for （int j = 0 ; j <= 20 ; j++ ）{
for （int k = 0 ;k < 2 ; k ++ ）
dp[j][i][k] = 0 ;
}
}
double ans = 0 ;
for （int i = 0 ; i <= 20 ; i ++ ）{
if（a[0] & （1 《 i））
dp[i][0] = 1 ;
else dp[i][0][0] = 1 ;
for （int j = 1 ; j <= n ; j ++ ）{
dp[i][j] = dp[i][j - 1] * p[j] ;//该位不取
dp[i][j][0] = dp[i][j - 1][0] * p[j] ;//该位不取
if（a[j] & （1 《 i））{//取该位
if（b[j] == '&'）{
dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
}
else if（b[j] == '|'）{
dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
dp[i][j] += dp[i][j - 1][0] * （1 - p[j]） ;
}
else {
dp[i][j] += dp[i][j - 1][0] * （1 - p[j]） ;
dp[i][j][0] += dp[i][j - 1] * （1 - p[j]） ;
}
}
else {//同理
if（b[j] == '&'）{
dp[i][j][0] += dp[i][j - 1] * （1 - p[j]） ;
dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
}
else if（b[j] == '|'）{
dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
}
else {
dp[i][j][0] += dp[i][j - 1][0] * （1 - p[j]） ;
dp[i][j] += dp[i][j - 1] * （1 - p[j]） ;
}
}
}
ans += （1 《 i） * dp[i][n] ;
}
printf（"Case %d:\n%.6f\n",++ca ,ans） ;
}
return 0 ;
} |