ZOJ 3329 One Person Game：期望dp【关于一个点成环—

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3329

题意：

　　给你面数分别为k1,k2,k3的三个骰子。

　　给定a,b,c三个整数。

　　三个骰子每扔一次，若骰子朝上的点数分别为a,b,c，则分数清零，否则当前分数+=骰子点数之和。

　　当分数 > n时游戏结束。

　　问你扔骰子次数的期望。

题意：

　　表示状态：

　　　　dp[i] = rest steps

　　　　（当前分数为i时，剩余步数的期望）

　　找出答案：

　　　　ans = dp[0]

　　　　刚开始分数为0。

　　如何转移：

　　　　由于此题中可以由高分数转移到低分数，所以转移存在环。

　　　　一般有环dp用高斯消元做。

　　　　但是，此题的所有环都跟dp[0]有关，也就是说所有的转移都能写成形如 dp[i] = a[i]*dp[0] + b[i] 的形式（分离系数）。

　　　　那么求出a[0]和b[0]就可以行了，答案为dp[0] = b[0] / (1-a[0])。

　　　　（1）dp[i] = sigma(dp[i+k]*p[k]) + dp[0]*p[0] + 1　（原转移方程，p[i]为扔出点数为i的概率,p[0]为扔出(a,b,c)的概率）

　　　　（2）dp[i] = a[i]*dp[0] + b[i]　（假设的）

　　　　将（2）代入（1）：

　　　　　　dp[i] = sigma( (a[i+k]*dp[0] + b[i+k]) * p[k] ) + dp[0]*p[0] + 1

　　　　　　dp[i] = sigma( a[i+k]*dp[0]*p[k] + b[i+k]*p[k] ) + dp[0]*p[0] + 1

　　　　　　dp[i] = ( sigma(a[i+k]*p[k]) + p[0] )*dp[0] + sigma(b[i+k]*p[k]) + 1

　　　　系数对应相等：

　　　　　　a[i] = sigma(a[i+k]*p[k]) + p[0]

　　　　　　b[i] = sigma(b[i+k]*p[k]) + 1

　　　　递推求出a[i] & b[i]即可，求的时候要保证i <= n（有意义）。

　　　　dp[0] = b[0] / (1-a[0])。

AC Code:

 // state expression:

 // dp[i] = rest steps

 // i: present score

 //

 // find the answer:

 // ans = dp[0]

 //

 // transferring:

 // 1) dp[i] = sigma(dp[i+k]*p[k]) + dp[0]*p[0] + 1

 // 2) dp[i] = a[i]*dp[0] + b[i]

 // ***solve:

 // dp[i] = sigma( (a[i+k]*dp[0] + b[i+k]) * p[k] ) + dp[0]*p[0] + 1

 // dp[i] = sigma( a[i+k]*dp[0]*p[k] + b[i+k]*p[k] ) + dp[0]*p[0] + 1

 // dp[i] = ( sigma(a[i+k]*p[k]) + p[0] )*dp[0] + sigma(b[i+k]*p[k]) + 1

 // ***result:

 // a[i] = sigma(a[i+k]*p[k]) + p[0]

 // b[i] = sigma(b[i+k]*p[k]) + 1

 // ***run:

 // cal a[i] & b[i]

 // dp[0] = b[0] / (1-a[0])

 //

 // boundary:

 // set a,b = 0

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 505

 #define MAX_K 40

 using namespace std;

 int n,t;

 int k1,k2,k3;

 int e1,e2,e3;

 double p[MAX_K];

 double a[MAX_N];

 double b[MAX_N];

 double dp[MAX_N];

 void read()

 {

     cin>>n>>k1>>k2>>k3>>e1>>e2>>e3;

 }

 void cal_pro()

 {

     memset(p,,sizeof(p));

     p[]=1.0/(k1*k2*k3);

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

     {

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

         {

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

             {

                 if(i!=e1 || j!=e2 || k!=e3)

                 {

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

                 }

             }

         }

     }

 }

 void cal_const()

 {

     memset(a,,sizeof(a));

     memset(b,,sizeof(b));

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

     {

         for(int k=;k<=k1+k2+k3;k++)

         {

             if(i+k>n) break;

             a[i]+=a[i+k]*p[k];

             b[i]+=b[i+k]*p[k];

         }

         a[i]+=p[];

         b[i]+=1.0;

     }

 }

 void solve()

 {

     cal_pro();

     cal_const();

     dp[]=b[]/(1.0-a[]);

 }

 void print()

 {

     printf("%.15f\n",dp[]);

 }

 int main()

 {

     cin>>t;

     while(t--)

     {

         read();

         solve();

         print();

     }

 }

巴特西

ZOJ 3329 One Person Game：期望dp【关于一个点成环——分离系数】

最新文章

热门文章