HDU4405（期望dp）

标准期望套路，很水。读题看好是到n就可以停止了。

 1 const int maxn = 1e5 + 50;
 2 int n, m;
 3 db dp[maxn];
 4 map<int, int> mp;
 5 
 6 int main() {
 7     while (~scanf("%d %d", &n, &m) && n) {
 8         rep(i, n, n + 5)    dp[i] = 0;
 9         mp.clear();
10         rep(i, 1, m) {
11             int a, b;
12             read(a), read(b);
13             mp[a] = b;
14         }
15 
16         db sum = 0;
17         irep(i, n - 1, 0) {
18             if (mp.count(i)) {
19                 dp[i] = dp[mp[i]];
20             } else {
21                 dp[i] = sum / 6 + 1.0;
22             }
23             sum += dp[i] - dp[i + 6];
24         }
25 
26         printf("%.4lf
", dp[0]);
27     }
28     return 0;
29 }