【期望DP】[zoj3329]One Person Game

﹏ヽ暗。殇╰゛Y 2023-06-01 06:09 8阅读 0赞

**题描：**

有三个均匀的骰子，分别有k1,k2,k3个面，初始分数是0，
    当掷三个骰子的点数分别为a,b,c的时候，分数清零，否则分数加上三个骰子的点数和，
    当分数>n的时候结束。求需要掷骰子的次数的期望。

令f\[i\]为当前三个骰子点数和为i时掷骰子期望次数

**则易有：(逆推)**

$$f\[i\]=\\sum(\{p\[k\]\*f\[i+k\]\})+f\[0\]\*P\_0+1$$

然而这是逆推...

咱并不知道$f\[0\]$的值

凉了

吗？

注意到求$f\[i\]$时跟它有关的所有f\[k\]中只有f\[0\]是未知的，那我们就把这玩意儿当做未知数

列方程：

令$f\[i\]=A\_i\*f\[0\]+B\_i$(①),则有：

$$f\[i+k\]=A\_\{i+k\}\*f\[0\]+B\_\{i+k\}$$

代入①式有：

$$f\[i\]=\\sum\[p\[k\]\*(A\_\{i+k\}\*f\[0\]+B\_\{i+k\})\]+f\[0\]\*P\_0+1$$

(②)

(p\[k\]表示三个骰子掷出和为k时的概率)

变形得：

$$f\[i\]=\[\\sum(p\[k\]\*A\_\{i+k\})+P\_0\]\*f\[0\]+\\sum(p\[k\]\*B\_\{i+k\})+1$$

（③）

这样就能发现③式与①式的形式已经大致相同了.

综上：

$$A\_i= \\sum(p\[k\]\*A\_\{i+k\})+P\_0$$

$$B\_i=\\sum(p\[k\]\*B\_\{i+k\})+1$$

令：$i=0$

有：

$$f\[0\]=A\_0\*f\[0\]+B\_0$$

综上：$$f\[0\]=\\frac\{B\_0\}\{1-A\_0\}$$

而f\[0\]就是我们最后要求的答案

所以我们只需要求a\[\]和b\[\]就可以啦

1 #include<bits/stdc++.h>
     2 #define writeln(x)  write(x),puts("")
     3 #define writep(x)   write(x),putchar(' ')
     4 using namespace std;
     5 inline int read(){
     6     int ans=0,f=1;char chr=getchar();
     7     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     8     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
     9     return ans*f;
    10 }void write(int x){
    11     if(x<0) putchar('-'),x=-x;
    12     if(x>9) write(x/10);
    13     putchar(x%10+'0');
    14 }const int M = 705;
    15 int k[M],q[M],n;
    16 double P,p[M],a[M],b[M];
    17 inline void Clear_All(){memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),memset(p,0,sizeof(p));} 
    18 int main(){
    19     int T=read();
    20     while(Clear_All(),T--){
    21         n=read();
    22         for(int i=0;i<=2;i++) k[i]=read();
    23         for(int i=0;i<=2;i++) q[i]=read();
    24         P=1.0/(k[0]*k[1]*k[2]);
    25         for(int i=1;i<=k[0];i++)
    26             for(int j=1;j<=k[1];j++)
    27                 for(int w=1;w<=k[2];w++)
    28                     if(i!=q[0]||j!=q[1]||w!=q[2])
    29                         p[i+j+w]+=P;
    30         for(int i=n;i>=0;i--){
    31             a[i]=P,b[i]=1;
    32             for(int j=0;j<=k[0]+k[1]+k[2];j++)
    33                 a[i]+=a[i+j]*p[j],b[i]+=p[j]*b[i+j];
    34         }printf("%.15lf\n",b[0]/(1-a[0]));
    35     }return 0;
    36 }

转载于:https://www.cnblogs.com/zhenglw/p/11283371.html