HDU 4405 Aeroplane chess 概率dp

HDU 4405 Aeroplane chess 概率dp

題意：玩飛行棋，棋盤有0~n共n+1，每次拋一個6面的骰子，若得到x(1<=x<=6)點，則從i走到i+x格。其中，有些格子是飛機場，只要站在第A格上，就會從第A格直接飛到第B格。當你站在第k格且k >= n時，游戲結束。求拋骰子次數的期望。

解釋概率dp加上一個限制條件，說下為什麼當有飛機的時候前面的等於後面的，因為dp代表的是當前位置到n的期望， 所以前面的概率等於飛機到達的

轉載：

又一道期望DP，其實這題與hdu4576那道概率DP很像（這道我也寫了題解）。那麼這兩道一道求概率，一道求期望，又能放在一起對比一下了，期望和概率的求法的不同。

先總結一句話：一般求概率DP或者是遞推的問題，都是正著推，從初始狀態往結束狀態（結束狀態一般是此類題要求的狀態）推，所以先得到（或者說先已知）的是靠近初始狀態的狀態，所以想要求的當前狀態是由可轉移到此狀態的前N可能個狀態推過來的；而一般求期望DP，都是逆著推，從結束狀態往初始狀態（初始狀態往往是此類題要求的狀態）推，所以先得到（或者說先已知）的是靠近結束狀態的狀態，所以想要求的當前狀態是由此狀態對應接下來的N可能個狀態推過來的。

本題題意：數軸上有N+1個點（編號0~N），一個人玩游戲，從0出發，當到達N或大於N的點則游戲結束。每次行動擲骰子一次，骰子編號1-6，擲到多少就向前走幾步，這個數軸上還有些特殊點，這些點類似飛行棋中的飛行點，只要到達這些點就可以直接飛到給定點。求總共投擲骰子次數的期望。

例如本題，倒著過來分析。用dp[i]表示在i位置時，距離游戲結束還要投擲次數的期望。顯然dp[n]為0，需要求的是dp[0]。對於直接飛過去的點。例如用數組vis[]來表示，vis[a]=b，表示當到達a點時可以直接飛到b點，那麼顯然dp[vis[a]]=dp[a]。倒著推，dp[i](假設該點不屬於可飛行的點)的下面一個狀態有6種可能（即對應6種可能的骰子數），每種都是1/6的概率。所以for(int x=1;x<=6;x++)dp[i]+=dp[i+x]/6.0;dp[i]+=1;注意最後加玩每種可能性的期望後要+1，因為這6種可能性加起來只是下一個狀態的期望，當前狀態是他們的前一個狀態，所以期望（直接理解為投擲骰子的次數）要+1

Description

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

 1.1667
2.3441 

#include
#include
#include
#include
#include
using namespace std;
int f[100005];
double dp[100005];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        if(n==0&&m==0)
            break;
        memset(f,0,sizeof(f));
        for(int i=0; i=0; i--)
        {
            if(f[i])
            {
                dp[i]=dp[f[i]];
            }
            else
            {
                for(int j=i+1; j<=i+6; j++)
                    dp[i]+=dp[j];
                dp[i]=dp[i]/6+1;
            }
        }
        printf("%.4f\n",dp[0]);
    }
    return 0;
}