【ZOJ3329】One Person Game

时间:2022-12-20 20:05:35

题意

你有三枚色子,第i个色子有ki面,你有一个计数器。

1.开始的时候将计数器调至0

2.扔三个色子,如果色子1是a,色子2是b,色子3是c,则将计数器归零。否则计数器加上三个色子的和。

3.如果计数器的数字大于等于n游戏结束,否则重复步骤

计算扔色子次数的期望

分析

通过带入系数解决概率DP问题。

f[i]为当前计数器的数字是i,到游戏结束的期望次数是多少。

f[i]=sum(f[i+k]*p)+1+f[0]*p。

因为f[0]就是我们所求的东西,所以我们令f[i]=A[i]*f[0]+B[i]

带入整理得f[i]=(sum(A[i+k]*p)+p)*f[0]+sum(p*B[i+k])+1

观察得到 A[i]=sum(p*A[i+k])+p

B[i]=sum(p*B[i+k])+1

ans=f[0]=B[0]/(1-A[0])

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int maxn=;
double A[maxn],B[maxn];
int T,n,K1,K2,K3,a,b,c; int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%d%d%d%d%d%d%d",&n,&K1,&K2,&K3,&a,&b,&c);
memset(A,,sizeof(A));
memset(B,,sizeof(B));
for(int i=;i<=n;i++){
for(int j=;j<=K1;j++){
for(int k=;k<=K2;k++){
for(int l=;l<=K3;l++){
if(j!=a||k!=b||l!=c){
int sum=j+k+l;
if(i-sum>=){
A[i]+=A[i-sum]*(double)/(K1*K2*K3);
B[i]+=B[i-sum]*(double)/(K1*K2*K3);
}
}
}
}
}
A[i]+=(double)/(K1*K2*K3);
B[i]+=;
}
double ans=B[n]/(-A[n]);
printf("%.15f\n",ans);
}
return ;
}