首页 > 代码库 > fzu1342

fzu1342

http://acm.fzu.edu.cn/problem.php?pid=1342

 

dp[i][j]  , i位尾巴为j的概率

const  int  maxn = 1008 ;double  dp[maxn][12] ;int  main(){     int i , j , n , k  ;     double  t  ;     while(cin>>k>>n){          for(i = 0 ; i <= k ; i++) dp[1][i] = 100.0 / double(k+1) ;          for(i = 2 ; i <= n ; i++){              dp[i][0] = (dp[i-1][0] + dp[i-1][1]) / double(k+1) ;              for(j = 1 ; j < k ; j++)                 dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]) / double(k+1) ;              dp[i][k] =  (dp[i-1][k-1] + dp[i-1][k]) / double(k+1) ;          }          for(t = 0.0 , i = 0  ; i <= k ; i++) t += dp[n][i] ;          printf("%.5lf\n" , t) ;     }     return 0 ;}

  

 

fzu1342