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

hdu-4089-Activation-概率dp

編輯:C++入門知識

kuangbin題解寫的很好,我就不贅余了。。

一下解釋來自kuangbin:

題意:有n個人排隊等著在官網上激活游戲。Tomato排在第m個。
對於隊列中的第一個人。有一下情況:
1、激活失敗,留在隊列中等待下一次激活(概率為p1)
2、失去連接,出隊列,然後排在隊列的最後(概率為p2)
3、激活成功,離開隊列(概率為p3)
4、服務器癱瘓,服務器停止激活,所有人都無法激活了。
求服務器癱瘓時Tomato在隊列中的位置<=k的概率


解析:
概率DP;
設dp[i][j]表示i個人排隊,Tomato排在第j個位置,達到目標狀態的概率(j<=i)
dp[n][m]就是所求
j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4;
2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4;
k 化簡:
j==1: dp[i][1]=p*dp[i][i]+p41;
2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41;
k

其中:
p=p2/(1-p1);
p31=p3/(1-p1)
p41=p4/(1-p1)


可以循環i=1->n 遞推求解dp[i].在求解dp[i]的時候dp[i-1]就相當於常數了。
在求解dp[i][1~i]時等到下列i個方程
j==1: dp[i][1]=p*dp[i][i]+c[1];
2<=j<=k:dp[i][j]=p*dp[i][j-1]+c[j];
k 其中c[j]都是常數了。上述方程可以解出dp[i]了。
首先是迭代得到 dp[i][i].然後再代入就可以得到所有的dp[i]了。


注意特判一種情況。就是p4

#include
#include
#include
#include
#include
#include
using namespace std;
#define eps 1e-9
#define zero(x) ((fabs(x)

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