HDU 4405 Aeroplane chess：期望dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4405

题意：

　　你在下简化版飞行棋。。。

　　棋盘为一个线段，长度为n。

　　上面有m对传送门，可以直接将你从a[i]传送到b[i]处。

　　每扔一次骰子，可以向前移动的步数为骰子的点数。

　　你的初始位置为0。当位置>=n时，游戏结束。

　　问你扔骰子次数的期望。

题解：

　　表示状态：

　　　　dp[i] = rest steps

　　　　位置为i时，剩余需要掷骰子次数的期望。

　　找出答案：

　　　　ans = dp[0]（初始位置）

　　如何转移：

　　　　每次掷骰子点数分别为1至6的概率均为1/6。

　　　　dp[i] = sigma (dp[i+j] * 1/6) + 1

　　　　特别地，当i为某个传送门的入口时，只能转移到出口处。所以此时dp[i] = dp[trans[i]].

　　边界条件：

　　　　set dp = 0

　　　　i >= n表明游戏已经结束，dp[i]为0.

　　　　i < n的dp[i]会在for循环中更新，所以不用管。

AC Code:

// state expression:
// dp[i] = rest steps
// i: present pos
//
// find the answer:
// ans = dp[0]
//
// transferring:
// now: dp[i]
// dp[i] = sigma (dp[i+j] * 1/6) + 1
//
// boundary:
// set dp = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100010

using namespace std;

int n,m;
int trans[MAX_N];
double dp[MAX_N];

void read()
{
    memset(trans,-1,sizeof(trans));
    int a,b;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        trans[a]=b;
    }
}

void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=n-1;i>=0;i--)
    {
        if(trans[i]!=-1)
        {
            dp[i]=dp[trans[i]];
            continue;
        }
        for(int j=1;j<=6;j++)
        {
            dp[i]+=dp[i+j]/6.0;
        }
        dp[i]+=1.0;
    }
}

void print()
{
    printf("%.4f
",dp[0]);
}

int main()
{
    while(cin>>n>>m)
    {
        if(n==0 && m==0) break;
        read();
        solve();
        print();
    }
}