hdu 4652 Dice(期望) - c++编程基础

TOP

hdu 4652 Dice(期望)

2015-07-20 17:43:05 来源: 作者: 【大中小】浏览:1次

Tags：hdu 4652 Dice 期望

掷一枚骰子，有m个面，问掷出连续出现n个相同的面以及连续出现n个两两不同的面的期望。

设dp[i]表示已经掷出i个相同/不同的面的期望，可以确定终态dp[n] = 0，

对于出现连续n个相同的面有

dp[i] = 1/m * dp[i+1] + (m-1)/m*dp[1] + 1

再列一个式子 dp[i+1] = 1/m * dp[i+2] + (m-1)/m * dp[1] + 1

两式相减得dp[i+1] - dp[i] = 1/m * (dp[i+2] - d[i+1])，可以发现任意连续的两数之差成等比数列，就可以求出dp[0]。

对于出现n个两两不同的面有

dp[i] = (m-1)/m * dp[i+1] + 1/m * (dp[1] + dp[2] + ...+ dp[i])

再列一个式子dp[i+1] = (m-1)/m * dp[i+2] + 1/m*(dp[1] + dp[2] +....+dp[i+1])

两式相减得dp[i+1] - dp[i] = (m-i-1)/m * (dp[i+1] - dp[i+2])，最后各个连续的式子相减也能求出dp[0]。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL __int64 #define LL long long #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100010; int main() { int test; int order,m,n; while(~scanf(%d,&test)) { for(int i = 1; i <= test; i++) { scanf(%d %d %d,&order,&m,&n); double ans = 1; if(order == 0) { double p = m*1.0,tmp = m*1.0; for(int i = 1; i <= n-1; i++) { ans += tmp; tmp *= p; } } else { double tmp = 1.0; for(int i = 1; i <= n-1; i++) { tmp *= m*1.0/(m-i); ans += tmp; } } printf(%.9lf ,ans); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Memset给非字符型数组进行赋值	下一篇：Matlab基础学习--------函数句柄

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: