bzoj4008

期望DP和概率DP Fi,j×Fi,j× (1−pi+1)j−>Fi+1,j(1−pi+1)j−>Fi+1,j 1−(1−pi+1)j−>Fi+1,j−1 #include<cstdio> #include<cctype> #include<cstring> using namespace std; int n,r,d[222]; double p[222],f[222][134],pw[222][134]; //f[i][j]表示当前到了第i个(发动了技能)，还剩j轮未发动技能时的概率 inline void read(int &x){ char ch=getchar();x=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} } int main(){ int T;read(T); while(T--){ read(n);read(r); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++){ scanf("%lf",&p[i]); read(d[i]); pw[i][0]=1.0; for(int j=1;j<=r;j++)pw[i][j]=pw[i][j-1]*(1-p[i]);//pw[i][j]计算(1-p[i]) ^j,即接下来j轮均不被发动的概率 } double ans=0; f[0][r]=1; for(int i=0;i<n;i++) for(int j=0;j<=r;j++){ f[i+1][j]+=f[i][j]*pw[i+1][j]; if(j-1>=0){ f[i+1][j-1]+=f[i][j]*(1-pw[i+1][j]);//(1-pw[i+1][j]表示当前第j+1在接下来j轮中发动技能的概率 ans+=f[i][j]*(1-pw[i+1][j])*d[i+1];//因为只需加上当前一轮的，因此不是f[i+1][j-1]*... } } printf("%.10lf\n",ans); } }

 

转载于:https://www.cnblogs.com/MikuKnight/p/8906734.html

相关资源：JAVA上百实例源码以及开源项目