Re: [問題] 隨機2進位和k不連續1
題目問什麼就設什麼
令 dp[i][j] 代表 1...i 滿足條件的字串 (連續的 1 不超過 k 長)
且結尾洽有 j 個連續的 1 的機率為多少
則可以推出遞迴式 dp[1][1] = p[1], dp[1][0] = 1 - p[1], dp[1][j] = 0, for j≧2
k
dp[i][0] = Σdp[i-1][t]*(1 - p[i])
t=0
dp[i][j] = dp[i-1][j-1]*p[i]
直接做的話時間複雜度為 O(n^3), 對 n = 200 應該夠快...
不過似乎可以再壓成 O(n^2) ... 因為求和的動作比較單純
※ 引述《pigcat1315 (還是朋友?)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: dev-c++
: 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
: 無
: 問題(Question)：
: 是個作業但我想破頭了QQ~
: 2<=k<=n<=200
: n代表幾個bit k代表最多幾個連續1 且每個bit有1時機率
: ex:n=2 k=2 p1=0.9 p2=0.5 (機率由使用者給)
: 00=> 0.1*0.5 1
: 01=> 0.1*0.5 2
: 10=> 0.9*0.5 3
: 11=> 0.9*0.5 4
: ============================
: 取無兩個連續1 1+2+3 等於答案
: 補充說明(Supplement)：
: 我需要想法~"~ ,因為想過暴力應該是不可能 要跑2的兩百次方
: 又想過用離散來解~可是只能求出指定的無n連續1的個數~
: 但會不知道是哪幾bit又無法求出各項機率
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.146.28
推
10/09 18:02, , 1F
10/09 18:02, 1F
推
10/09 18:10, , 2F
10/09 18:10, 2F
推
10/09 19:31, , 3F
10/09 19:31, 3F
推
10/09 20:16, , 4F
10/09 20:16, 4F
→
10/10 02:22, , 5F
10/10 02:22, 5F
→
10/10 03:09, , 6F
10/10 03:09, 6F
解是 dp[n][0] + dp[n][1] + dp[n][2] + ... + dp[n][k],
因為 dp[i][j] 代表 1...i 滿足條件的字串 (連續的 1 不超過 k 長),
且結尾洽有 j 個連續的 1 的機率為多少
不過突然發現我算的跟原 po 舉得例子不太一樣 ... 我會把 k 個連續的也算進去.
1100 存在的路線大概是 dp[1][1] -> dp[2][2] -> dp[3][0] -> dp[4][0]
※ 編輯: suhorng 來自: 59.115.146.28 (10/10 10:14)
推
10/10 18:28, , 7F
10/10 18:28, 7F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
