hdu 4649 Professor Tian 反状态压缩+概率DP

思路:反状态压缩——把数据转换成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[i-1][0]*p[i]+根据不同运算符和第i位的值运算得到0的概率。

初始状态:f[0][0~1]=0或1(根据第一个数的该位来设置)

每一位为1的期望 f[n][1]

这题只要知道怎样表示状态就很简单了!!!以上是标程……

代码如下:

 #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
double dp[][],p[];
char str[];
int f[];
double fun1(int i,int j){//位运算结果为1的期望值
double ans=0.0,pp=-p[i];
int t=(f[i]>>j)&;
if(str[i]=='&'&&t){
ans=dp[i-][]*pp;
}
else if(str[i]=='|'){
ans=dp[i-][]*pp;
if(t==)
ans+=dp[i-][]*pp;
}
else if(str[i]=='^'){
if(t==)
ans=dp[i-][]*pp;
else ans=dp[i-][]*pp;
}
return ans;
}
double fun0(int i,int j){//位运算结果为0的期望值
double ans=0.0,pp=-p[i];
int t=(f[i]>>j)&;
if(str[i]=='&'){
if(t==)
ans=dp[i-][]*pp;
else ans=(dp[i-][]+dp[i-][])*pp;
}
else if(str[i]=='|'&&t==)
ans=dp[i-][]*pp;
else if(str[i]=='^'){
if(t==) ans=dp[i-][]*pp;
else ans=dp[i-][]*pp;
}
return ans;
}
int main(){
int c,n,i,j,k=;
double ans;
while(scanf("%d",&n)!=EOF){
for(i=;i<=n;i++) scanf("%d",&f[i]);
for(i=;i<=n;i++) scanf("%s",&str[i]);
for(i=;i<=n;i++) scanf("%lf",&p[i]);
ans=0.0;
for(i=;i<;i++){
c=(f[]>>i)&;
dp[][]=c; dp[][]=c^;
for(j=;j<=n;j++){
dp[j][]=dp[j-][]*(p[j])+fun1(j,i);
dp[j][]=dp[j-][]*(p[j])+fun0(j,i);
}
ans+=(<<i)*dp[n][];
}
printf("Case %d:\n%.6lf\n",++k,ans);
}
return ;
}

上一篇:教程 | 一文入门Python数据分析库Pandas


下一篇:WPF设置窗口模式(Windowstyle=“None”)