zoj 3329 One Person Game 概率DP

思路：这题的递推方程有点麻烦！！

dp[i]表示分数为i的期望步数，p[k]表示得分为k的概率，p0表示回到0的概率：

dp[i]=Σ(p[k]*dp[i+k])+dp[0]*p0+1

设dp[i]=A[i]*dp[0]+B[i]带入的：

dp[i]=∑(pk*A[i+k]*dp[0]+pk*B[i+k])+dp[0]*p0+1
       =(∑(pk*A[i+k])+p0)dp[0]+∑(pk*B[i+k])+1;
     明显A[i]=(∑(pk*A[i+k])+p0)
     B[i]=∑(pk*B[i+k])+1
     先递推求得A[0]和B[0].
     那么  dp[0]=B[0]/(1-A[0]);

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754

代码如下：

 #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 600

 using namespace std;

 double p[],A[MAX],B[MAX],p0;

 int main(){

     int n,i,j,t,k,s,k1,k2,k3,a,b,c;

     cin>>t;

     while(t--){

         cin>>n>>k1>>k2>>k3>>a>>b>>c;

         p0=1.0/k1/k2/k3;

         memset(p,,sizeof(p));

         for(i=;i<=k1;i++)

         for(j=;j<=k2;j++)

         for(k=;k<=k3;k++){

             if(i!=a||j!=b||k!=c)

                 p[i+j+k]+=p0;

         }

         memset(A,,sizeof(A));

         memset(B,,sizeof(B));

         for(i=n;i>=;i--){

             A[i]=p0;B[i]=;

             for(j=;j<=k1+k2+k3;j++){

                 A[i]+=A[i+j]*p[j];

                 B[i]+=B[i+j]*p[j];

             }

         }

         printf("%.15lf\n",B[]/(1.0-A[]));

     }

     return ;

 }

zoj 3329 One Person Game 概率DP的相关教程结束。