程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4405Aeroplane chess 概率dp水題

hdu4405Aeroplane chess 概率dp水題

編輯:C++入門知識

hdu4405Aeroplane chess 概率dp水題


//從0到n有n+1個格子
//對於格子i,擲一次骰子的數為x,那麼可以從位置i到位置i+x
//格子之間有連線,如果格子a和b有連線,那麼從a到b不用擲骰子
//求從0到n的骰子擲的次數的期望
//dp[i] = 1/6*segma(dp[k]) + 1 (i<=k<=i+6)
#include
#include
#include
using namespace std ;
const int maxn = 100000 ;
double dp[maxn] ;
int line[maxn] ;
int main()
{
int n , m ;
while(scanf(%d%d , &n ,&m) && n+m)
{
memset(line , -1 , sizeof(line)) ;
memset(dp , 0 ,sizeof(dp)) ;
int a , b ;
for(int i = 1;i <= m ;i++)
{
scanf(%d%d ,&a , &b) ;
line[a] = b ;
}
for(int i = n-1 ;i >= 0 ;i--)
{
if(line[i] != -1){dp[i] = dp[line[i]] ;continue;}
for(int k = i + 1;k <= i+6 ;k++)
dp[i] += ((double)1/(double)6)*dp[k];
dp[i] += 1 ;
}
printf(%.4lf , dp[0]) ;
}
return 0 ;
}
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved