【題意】：
跳格子，左右腳輪流跳，不能往回跳，每次跳有個[A , B]步長范圍。每個格子可能出現(xiàn)四種狀態(tài)，可右腳進(jìn)，左腳進(jìn)，雙腳進(jìn)，不準(zhǔn)進(jìn)。每種狀態(tài)都有一定概率。每次只能跳到最近可行的格子。當(dāng)跳出了n個格子或者不能動時期望步數(shù)。
【題解】：期望類題目，無環(huán)，直接dp。
利用全期望公式，注意狀態(tài)枚舉時要乘上條件概率。然后按常規(guī)期望做法即可，倒著推。答案為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<int, int> 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