題意:
(from luckycat)
解法:
因為最多有 2^100 種結果，所以看起來就很 DP。
我們考慮第 n 次的丟擲結果 (H、T) 且將它放到前 n-1 次結果的前面。
所以定義 dp[ n ][ k ][ pre ] 為當丟擲了 n 次且其中最長的連續 H 長度為 k 且結果串從最前面算起來最長連續 H 的長度。舉個例子： HHTHHHT 此結果串就屬於 dp[ 7 ][ 3 ][ 2 ] 裡面！
遞迴式：
dp[ n ][ k ][ pre ] =
{ 1, if k = pre = 0
{ dp[ n-1 ][ k-1 ][ pre-1 ]+dp[ n-1 ][ k ][ pre-1 ], if k and pre > 0
{ sum( dp[ n-1 ][ k ][ u ], 0 <= u <= k ), if k > 0 and pre = 0
TAG: DP, BigNum
注意: 因為答案會到 2^100-1，所以要用大數喔！
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽