HDU 4405 Aeroplane chess(確率DP&期待)
6905 ワード
Aeroplane chess
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 660 Accepted Submission(s): 468
Problem Description
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 (0Please 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≤XiThe 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
Source
2012 ACM/ICPC Asia Regional Jinhua Online
Recommend
zhoujiaqi2010
http://kicd.blog.163.com/blog/static/126961911200910168335852/
n個の方程式、持ち帰ればいいです.e[n]=0である、全ての符号iがnより大きい所望値e[i]も0である.
読んでいない人がいるようですが、例を書きます.
例えばn=3,m=0
列挙された方程式はe[0]=1/6 e[1]+1/6 e[2]+1/6 e[3]+1である.
e[1]=1/6e[2]+1/6e[3]+1
e[2]=1/6e[3]+1
e[3]=0
0という点から1,2,3,4,5,6までの位置は,3ゲーム終了以上で,所望の投色子回数がなくなるため,3以上の格子にジャンプしても期待値は0となる.
したがって,n個の方程式をリストした後,直接バンドバックすればe[0]を求めることができる.e[3]=0のようにe[2]=1を求めることができる、e[2]とe[3]が既知であればe[1]を求めることができ、さらにe[0]を求めることができる.
2層forサイクルはバンドバックの過程である.
テーマはまた直接aからbにジャンプすることができて、色子を投げる必要はありませんて、そのように直接マークして、aの期待値もbの期待値に等しいです.(a
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 660 Accepted Submission(s): 468
Problem Description
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
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
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
Source
2012 ACM/ICPC Asia Regional Jinhua Online
Recommend
zhoujiaqi2010
http://kicd.blog.163.com/blog/static/126961911200910168335852/
n個の方程式、持ち帰ればいいです.e[n]=0である、全ての符号iがnより大きい所望値e[i]も0である.
読んでいない人がいるようですが、例を書きます.
例えばn=3,m=0
列挙された方程式はe[0]=1/6 e[1]+1/6 e[2]+1/6 e[3]+1である.
e[1]=1/6e[2]+1/6e[3]+1
e[2]=1/6e[3]+1
e[3]=0
0という点から1,2,3,4,5,6までの位置は,3ゲーム終了以上で,所望の投色子回数がなくなるため,3以上の格子にジャンプしても期待値は0となる.
したがって,n個の方程式をリストした後,直接バンドバックすればe[0]を求めることができる.e[3]=0のようにe[2]=1を求めることができる、e[2]とe[3]が既知であればe[1]を求めることができ、さらにe[0]を求めることができる.
2層forサイクルはバンドバックの過程である.
テーマはまた直接aからbにジャンプすることができて、色子を投げる必要はありませんて、そのように直接マークして、aの期待値もbの期待値に等しいです.(a
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
double res[N];
int father[N];
int main(){
//freopen("input.txt","r",stdin);
int n,m;
while(~scanf("%d%d",&n,&m)){
if(n==0 && m==0)
break;
memset(res,0,sizeof(res));
memset(father,-1,sizeof(father));
int a,b;
while(m--){
scanf("%d%d",&a,&b);
father[a]=b;
}
for(int i=n-1;i>=0;i--){
if(father[i]!=-1)
res[i]=res[father[i]];
else{
for(int j=1;j<=6;j++){
if(i+j<=n)
res[i]+=1.0/6*res[i+j];
else
break;
}
res[i]+=1;
}
}
printf("%.4lf
",res[0]);
}
return 0;
}