loj 1030概率dp

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 const int MAXN = (100 + 10);
 9 double dp[MAXN], num[MAXN];
10 int n;
11 
12 int main()
13 {
14     int _case, t = 1;
15     scanf("%d", &_case);
16     while (_case--) {
17         scanf("%d", &n);
18         for (int i = 1; i <= n; i++) {
19             scanf("%lf", &num[i]);
20         }
21         memset(dp, 0, sizeof(dp));
22         dp[n] = num[n];
23         for (int i = n - 1; i >= 1; i--) {
24             int d = min(6, n-i);
25             dp[i] = num[i];
26             for (int j = 1; j <= d; j++) {
27                 dp[i] += dp[i+j]/d;
28             }
29         }
30         printf("Case %d: %.7lf\n", t++, dp[1]);
31     }
32     return 0;
33 }