简单概率DP——hdu4405

题目描述:

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题,几行代码搞定,也很容易理解,贴上代码,算是我的概率DP入门题:

/*******************************************************************************/
/* OS           : Linux fc20.x86_64 #1 SMP Tue Dec  UTC 2013 x86_64  GNU/Linux
 * Compiler     : 4.8.2 20131212 (Red Hat 4.8.2-7) (GCC)
 * Encoding     : UTF8
 * Date         : 2014-04-02
 * All Rights Reserved by alop.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005
int x[N],y[N],mp[N];
double dp[N];
int main()
{
     //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
   int n,m;
   while(cin>>n>>m&&(n||m))
   {
       int i=0;
       memset(mp,-1,sizeof(mp));
       memset(dp,0,sizeof(dp));
       while(i++<m)
       {
           cin>>x[i]>>y[i];
           mp[x[i]]=y[i];
       }
       for(i=n-1;i>=0;i--)
       {
           if(mp[i]!=-1)dp[i]=dp[mp[i]];
           else
           {
               for(int j=1;j<=6;j++)
                dp[i]+=dp[i+j];
               dp[i]=dp[i]/6+1;
           }
       }
       printf("%.4f\n",dp[0]);

   }
   return 0;
}

简单概率DP——hdu4405

时间: 05-03

简单概率DP——hdu4405的相关文章

POJ 3071 Football(简单 概率DP)

Football 原文链接:http://blog.csdn.net/xuechelingxiao/article/details/38520105 大意:2^n 个球队进行单场淘汰赛,每两只球队之间比赛会有胜负的概率,问最后谁夺冠的概率最大. 思路:简单的概率DP问题,主要是怎么处理哪两个球队比赛的问题. DP方程为 dp[i][j] = ∑(dp[i-1][j]*dp[i-1][k]*p[j][k]); //dp[i][j]表示第 i 轮的时候,第 j 支队伍赢的概率.. 对于其中位运算,可

Aeroplane chess(简单概率dp)

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). Whe

poj 3071 简单概率dp

题意很清晰,就是问最有可能获得冠军的队伍. 需要注意的是每轮比赛中,每个队都是和自己旁边的一个队比赛,采用淘汰赛制,所以需要决定第i轮的时候j队可以和哪些队比赛,然后求概率dp即可. 状态转移方程: dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * p[j][k]; dp[i][j]表示第i轮j队获胜的概率 = 第i-1轮j队获胜的概率 * 第i-1轮k队获胜的概率 * j队打败k队的概率(之和). 前提是j和k在第i轮可能遇到. 判断方法: ( j >> (

Josephina and RPG 简单概率DP

Josephina and RPG 题目抽象:给出R=C(m,3)个队伍之间的胜率.给出需要挑战的n个队伍(按顺序).玩家最开始从R个队伍中任选一支队伍去挑战,当挑战某队伍成功时,可以将当前的队伍与挑战成功的队伍交换,也可以继续选择该队伍.  求最大的胜率. 思路:物理递推法. /*                    dp[i+1][j]            dp[i][j]=                    dp[i+1][num[i]]*/ 1 #include <iostrea

CodeForces 540D Bad Luck Island 概率dp

CodeForces 540D 应该是简单概率dp,由于写得少显得十分蠢萌 求期望逆推,求概率正推,大概是这么个意思,贴一发留恋 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define db double const int maxn=108; db dp[maxn][maxn][maxn]; int main() { int i,j,n,m,k,p; whi

Throwing Dice(概率dp)

C - Throwing Dice Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu LightOJ 1064 uDebug Description n common cubic dice are thrown. What is the probability that the sum of all thrown dice is at least x? Input Input starts wit

hdu 3853 概率DP 简单

http://acm.hdu.edu.cn/showproblem.php?pid=3853 题意:有R*C个格子,一个家伙要从(0,0)走到(R-1,C-1) 每次只有三次方向,分别是不动,向下,向右,告诉你这三个方向的概率,以及每走一步需要耗费两个能量,问你走到终点所需要耗费能量的数学期望: 回头再推次,思想跟以前的做过的类似 注意点:分母为0的处理 #include <cstdio> #include <cstring> #include <algorithm>

hdu--4576--概率dp&lt;见过最简单的概率dp&gt;

看到 expected possibility 一下子 又觉得是概率dp了.. 这题 也的确是了 但做的狠无语啊  尝试了2种  一个是TLE 一个是AC 但也要花掉了3000多ms.. 而且 我也觉得这两种 区别不大啊 思想是一样的 就是处理上有点区别.. 应该是第二种TLE的故意被卡了时间吧  my guess 这题的话 思路很简单 就是一层一层的递推下来 并且这一层的状态只与上一层有关~ 其实 每次可以选择走的方案数就是: 2^1 --> 2^2 --> 2^3 --> .....

hdu4405概率dp入门

Aeroplane chess Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1122    Accepted Submission(s): 762 Problem Description Hzz loves aeroplane chess very much. The chess map contains N+1 grids lab