# Aeroplane chess

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1581    Accepted Submission(s): 1082

Problem Description

Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When Hzz is at grid i and the dice number is x, he will moves to grid i+x. Hzz finishes the game when i+x is equal to or greater than N. There are also M flight lines on the chess map. The i-th flight line can help Hzz fly from grid Xi to Yi (0<Xi<Yi<=N) without throwing the dice. If there is another flight line from Yi, Hzz can take the flight line continuously. It is granted that there is no two or more flight lines start from the same grid. Please help Hzz calculate the expected dice throwing times to finish the game.

Input

There are multiple test cases. Each test case contains several lines. The first line contains two integers N(1≤N≤100000) and M(0≤M≤1000). Then M lines follow, each line contains two integers Xi,Yi(1≤Xi<Yi≤N).   The input end with N=0, M=0.

Output

For each test case in the input, you should output a line indicating the expected dice throwing times. Output should be rounded to 4 digits after decimal point.

Sample Input

2 0 8 3 2 4 4 5 7 8 0 0

Sample Output

1.1667 2.3441

Source

2012 ACM/ICPC Asia Regional Jinhua Online

dp【n】=0;因为在哪里不需要再跳，这个已知，所以可以倒退

dp[i]=sum{1+dp[n+j]}(1<=j<=6)

代码：

``` 1 #include<cstdio>
2 #include<cstring>
3 #include<stack>
4 #define maxn 100008
5 using namespace std;
6 double  dp[maxn];
7 stack<int> path[maxn];
8 int pa[maxn];
9 int main()
10 {
11   int n,m,a,b;
12   while(scanf("%d%d",&n,&m)!=EOF&&n+m)
13   {
14     memset(pa,0,sizeof(int)*(n+2));
15     memset(dp,0,sizeof(double)*(n+8));
16       while(m--)
17     {
18       scanf("%d%d",&a,&b);
19       path[b].push(a);
20       pa[a]=b;
21     }
22     while(--n>=0)
23     {
24       while(!path[n+1].empty())
25      {
26          dp[path[n+1].top()]=dp[n+1];
27          path[n+1].pop();
28      }
29       if(pa[n]==0)
30          dp[n]=1.0+(dp[n+1]+dp[n+2]+dp[n+3]+dp[n+4]+dp[n+5]+dp[n+6])/6.0;
31     }
32    printf("%.4lf\n",dp[0]);
33   }
34   return 0;
35 }```

0 条评论

• ### zoj3822 Domination（概率dp）

Domination ---- Time Limit: 8 Seconds      Memory Limit: 131072 KB      Specia...

• ### hdu---(3555)Bomb(数位dp（入门）)

Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Jav...

• ### hdu--（1025）Constructing Roads In JGShining's Kingdom（dp/LIS+二分）

Constructing Roads In JGShining's Kingdom Time Limit: 2000/1000 MS (Java/Others)...

• ### How to view past performance with sar in Linux

There are many tools/utilities that can be used to analyze the current system pe...

• ### 社交网络信息安全:规避云计算风险

云计算用在 BYOD 及社交网络这两种最新的、最热门的 IT 应用，特别会引起人们的注意，这是因为它们引起了新的安全问题。 第一个问题是: BYOD 为何会如此...

• ### LeetCode 第 16 场双周赛（402/822，前48.9%）

做出了2道题，第二道题耽搁时间有点长，放弃了，第四题在时间到了后一会就做出来了。

• ### 基本数据类型封装类

封装类里面的方法和特性都差不多，只要学会其中一个其他的也就会了，一般来讲用得比较多的是Integer，其他则用的比较少。