ZOJ 3329 One Person Game （概率DP）

ZOJ 3329 One Person Game （概率DP）

​​i+k!=0 ) （1）

抽象成：

（2）

（dp[i+k]含有dp[0]，所以不能简单地认为a[0]就是p[0]）

将

带入（1）计算，得到：

联系（2）得到：

这样一带一比就找到了a[i]和b[i]的递推式，很神奇啊有木有

当i=0时，有

因为dp(i>n)=0，所以有 a[i>n]=b[i>n]=0。

最后求得dp[0]即可。

#include #include #include using namespace std;int n,k1,k2,k3,A,B,C;double a[505],b[505];double p[20];int main(){ int t; cin>>t; while(t--){ scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&A,&B,&C); double one=1.0/k1/k2/k3; memset(p,0,sizeof(p)); for(int i=1;i<=k1;i++){ for(int j=1;j<=k2;j++){ for(int k=1;k<=k3;k++){ if(i==A&&j==B&&k==C) continue; p[i+j+k]+=one; } } } memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=n;i>=0;i--){ a[i]=one; //p0 b[i]=1.0; for(int j=3;j<=(k1+k2+k3);j++){ a[i]+=p[j]*a[i+j]; b[i]+=p[j]*b[i+j]; } } printf("%.15lf\n",b[0]/(1-a[0])); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。