題意:

飛行棋。有n+1格，開始時在0號格子，每一步都要扔一個dice（六個面，概率相同）哪一面朝上他就會向前走x+i步。當x+i大于等于N的時候，游戲結束。另外，地圖上有m條航線。第i條航線可以直接從xi到yi。計算扔dice次數的期望。

題目：

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

分析:

這個題有一個默認的條件，如果當前格子有航線可以選擇，那么就一定選擇航線而不是擲色子。
最簡單的概率DP，狀態的定義需要從后往前定義，因為航線的緣故只能從后往前轉移。

n個方程，回帶一下就行。f[n]=0,所有標號i大于n的期望值f[i]也為0. 有蟲洞 對于任何一個蟲洞，起點的期望等于終點的期望。
例子。
比如n=3,m=0
所列方程為f[0]=1/6f[1]+1/6f[2]+1/6f[3]+1
f[1]=1/6e[2]+1/6e[3]+1
f[2]=1/6e[3]+1
f[3]=0
從0這個點可以到1,2,3,4,5,6這幾個位置，由于大于等于3游戲結束，不會再有期望的投色子次數了，所以跳到3和大于3的格子里期望值也就都是0了。
所以我們列出n個方程后直接回帶就能把f[0]求出來。如f[3]=0可以求出f[2]=1,已知了f[2]和f[3]就可以求出f[1],進而求出f[0].
兩層for循環就是一個回帶的過程。
題目還有可以直接從a跳到b,不需要投色子的，那樣就直接標記一下，a的期望值也就等于b的期望值。(a<b)

定義f[i]為 從第i個格子到n個格子的期望次數是多少。
如果i格子有航線那么 f[i]=f[to] ,to是航線可以到達的格子。
如果i格子沒有航線，那么f[i]=sum(1/6*f[i+k])+1,其中k是色子的六個面(1,2,3,4,5,6)。

ac代碼：

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int M=1e5+10; int n,m; int dp[M]; double f[M]; int main() {while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){memset(f,0,sizeof(f));memset(dp,-1,sizeof(dp));int x,y;for(int i=1; i<=m; i++){scanf("%d%d",&x,&y);dp[x]=y;}for(int i=n-1; i>=0; i--){if(dp[i]!=-1)f[i]=f[dp[i]];elsefor(int j=1; j<=6; j++){int to=min(n,i+j);f[i]+=(f[to]+1)*(double)1/6;}}printf("%.4f\n",f[0]);}return 0; }

總結

以上是生活随笔為你收集整理的Aeroplane chess HDU - 4405（期望dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。