Re: [問題] 隨機2進位和k不連續1

[suhorng ( )]

題目問什麼就設什麼

令 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
推 firejox:有神快拜~~
推 tjjh89017:有神快拜
推 pigcat1315:><" 好多神~ 感謝大家 原來這要DP解
推 VictorTom:有神快拜Orz
→ bleed1979:解為1 - dp[n][k] - dp[n - 1][k] - ... - dp[k][k]
→ bleed1979:等等，dp[4][2]好像不會計算到1100這樣的case
解是 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)
推 xatier:有神快拜!