【题意】:跳格子,左右脚轮流跳,不能往回跳,每次跳有个[A , B]步长范围。每个格子可能出现四种状态,可右脚进,左脚进,双脚进,不准进。每种状态都有一定概率。每次只能跳到最近可行的格子。当跳出了n个格子或者不能动时期望步数。

【题解】:期望类题目,无环,直接dp。
              利用全期望公式,注意状态枚举时要乘上条件概率。然后按常规期望做法即可,倒着推。答案为dp[0][3]。

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<intint> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 
26 double dp[4010][4];
27 double p[4010][4];
28 int n, a, b;
29 int main() {
30     int T;
31     scanf("%d", &T);
32     while(T--) {
33         scanf("%d%d%d", &n, &a, &b);
34         memset(p, 0, sizeof(p));
35         memset(dp, 0, sizeof(dp));
36         for(int i = 1; i <= n; i++)
37             scanf("%lf%lf%lf%lf", &p[i][0], &p[i][1], &p[i][2], &p[i][3]);
38         for(int i = n + 1; i <= n + a; i++) p[i][3] = 1.0;
39         double c = 1.0;
40         for(int i = n; i >= 0; i--) {
41             for(int j = 1; j < 4; j++) {
42                 double pp = 1.0;
43                 for(int k = a; k <= b; k++) {
44                     if(j == 1) {
45                         dp[i][1] += pp * ((dp[i+k][2] + c) * p[i+k][2] + (dp[i+k][3] + c) * p[i+k][3]);
46                         pp *= (p[i+k][0] + p[i+k][1]);
47                     } else if(j == 2) {
48                         dp[i][2] += pp * ((dp[i+k][1] + c) * p[i+k][1] + (dp[i+k][3] + c) * p[i+k][3]);
49                         pp *= (p[i+k][0] + p[i+k][2]);
50                     } else if(j == 3) {
51                         dp[i][3] += pp * ((dp[i+k][1] + c) * p[i+k][1] + (dp[i+k][2] + c) * p[i+k][2] + (dp[i+k][3] + c) * p[i+k][3]);
52                         pp *= (p[i+k][0]);
53                     }
54                 }
55             }
56         }
57         printf("%.6f\n", dp[0][3]);
58     }
59     return 0;
60 }
61