题目链接：
https://vjudge.net/contest/170340#problem/C
题目大意：
有三个骰子，分别为k1,k2,k3面，同时，存在a,b,c，当三个骰子的点数恰好依次是a,b,c时，得分归零，否则得到三个骰子点数总和的分，求得分大于n的期望轮数是多少
分析：
概率正推，期望逆推，如果没有归零的条件，显然可以用dp[i]表示当前得分为i，到达目标的期望，写出dp转移式
dp[i]=k=3∑k<=k1+k2+k3dp[i+k]∗pk+1
pk表示得到k分的概率，那么加上归零这个条件，写出的转移式则应该是
dp[i]=k=3∑k≤k1+k2+k3dp[i+k]∗pk+dp[0]∗p0+1
而dp[0]就是我们所需要求的答案，是一个常数，在dp的过程中每一项都出现，所以可以将dp[0]设为未知量，则dp[i]都仅与dp[0]有关，设dp[i]
dp[i]=A[i]∗dp[0]+B[i]
最后将该式代入原转移式，得到
dp[i]=k=3∑k≤k1+k2+k3(A[i+k]∗dp[0]+B[i+k])∗pk+dp[0]∗p0+1
联立两式，显然又
A[i]=k=3∑k≤k1+k2+k3A[i+k]∗pk+p0
B[i]=k=3∑k≤k1+k2+k3B[i+k]∗pk+1
最后根据
dp[0]=A[0]∗dp[0]+B[0]
即可解得答案
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define inf 0x3fffffff
using namespace std;
double dp[200];
double A[600],B[600];
int n,k1,k2,k3,a,b,c;
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(dp,0,sizeof(dp));
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
dp[0] = 1.0/k1/k2/k3;
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;
dp[i+j+k] += dp[0];
}
}
}
for (int i = n ; i >= 0 ; i --)
{
for (int j = 3 ; j <= k1+k2+k3 ; j ++)
{
A[i]+= A[i+j]*dp[j];
B[i]+= B[i+j]*dp[j];
}
A[i]+=dp[0];
B[i]+=1;
}
printf("%.12f\n",B[0]/(1-A[0]));
}
}
|