HDU 4405 Aeroplane chess 期望dp

时间：2024-09-20 17:37:44

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4405

Aeroplane chess

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
#### 问题描述
> 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
> Please help Hzz calculate the expected dice throwing times to finish the game.
#### 输入
> 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 The input end with N=0, M=0.

输出

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.

样例输入

2 0

8 3

2 4

4 5

7 8

0 0

样例输出

1.1667

2.3441

题意

飞行棋，每次投掷骰子，(1-6等概率),按骰子大小前进，其中有若干个飞机场(a,b)，可以从a直接传送到b，现从0点出发，问到达>=N的点需要的期望步数。

题解

期望dp入门：

全期望公式：E[x]=sigma(pi*E[xi]).

有飞机场的话：E[a]=E[b]。

否则：E[i]=sigma(1/6*(E[i+x]+1)).

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=101010;

///dp[i]表示在i点，到达终点还需几步

///期望一般逆推求，比如这一题，你已知的状态是终点而不是起点。

double dp[maxn];

int mp[maxn];

int n,m;

void init(){

    clr(mp,-1);

    clr(dp,0);

}

int main() {

    while(scf("%d%d",&n,&m)==2&&n){

        init();

        rep(i,0,m){

            int u,v;

            scf("%d%d",&u,&v);

            mp[u]=v;

        }

        for(int i=n-1;i>=0;i--){

            ///有飞机场，直接飞过去

            if(mp[i]!=-1){

                dp[i]=dp[mp[i]];

                continue;

            }

            ///掷骰子,全期望公式

            for(int x=1;x<=6;x++){

                dp[i]+=1.0/6*(dp[i+x]+1);

            }

        }

        prf("%.4lf\n",dp[0]);

    }

    return 0;

}

//end-----------------------------------------------------------------------

相关文章