10328: Coin Toss ★★★☆☆ 題組：Problem Set Archive with Online Judge 解題者：張鈞富 解題日期：2019年4月11日 題意： 輸入兩數n, k(1 ≤ k ≤ n ≤ 100)，計算在連續投擲n次硬幣之所有情況中，有至少連續k次正面的情況的次數，並將其輸出
題意範例： Sample Input 4 1 4 2 //全部的組合-dp(4,1) = 16-8 = 8 4 3 4 4 6 2 Sample Output 15 8 3 1 43
解法：計算所有情況減去最多出現連續m次正面之情形 dp(n,m)=dp(n-1,m)*2-dp(n-m-2,m) dp(n,m)=丟n次硬幣其中最多連續m次正面 dp(n-1,m)*2=丟n-1次硬幣時就已經達成條件*2 (第n次分別為正反面的情形) dp(n-m-2,m)=前n-1次中的最後m次都是正面且第n次也是正面 (dp(n-1,m)) (正面) (dp(n-m-2),m)(反面)(m個正面) (正面)
dp(n,m) n m 1 2 3 4 5 7 8 13 15 16
4 2 => dp(4,1) = dp(3,1)*2-dp(1,1)=8 => 8 ○為反面 ⊕為正面 ○○○ ○ ˅ ○○○ ⊕ ⊕○○ ○ ⊕○○ ⊕ ○⊕○ ○ ○⊕○ ⊕ ⊕⊕○ ○ ⊕⊕○ ⊕ ○○⊕ ○ ○○⊕ ⊕ ⊕○⊕ ○ ⊕○⊕ ⊕ ○⊕⊕ ○ ○⊕⊕ ⊕ ⊕⊕⊕ ○ ⊕⊕⊕ ⊕
4 1 => dp(4,0)=1 => 16-1 => 15 解法範例: 4 1 => dp(4,0)=1 => 16-1 => 15 ○為反面 ⊕為正面 ○○○ ○ ˅ ○○○ ⊕ ⊕○○ ○ ⊕○○ ⊕ ○⊕○ ○ ○⊕○ ⊕ ⊕⊕○ ○ ⊕⊕○ ⊕ ○○⊕ ○ ○○⊕ ⊕ ⊕○⊕ ○ ⊕○⊕ ⊕ ○⊕⊕ ○ ○⊕⊕ ⊕ ⊕⊕⊕ ○ ⊕⊕⊕ ⊕
4 2 => dp(4,1)=8 => 16-8 => 8 ○為反面 ⊕為正面 ○○○ ○ ˅ ○○○ ⊕ ⊕○○ ○ ⊕○○ ⊕ ○⊕○ ○ ○⊕○ ⊕ ⊕⊕○ ○ ⊕⊕○ ⊕ ○○⊕ ○ ○○⊕ ⊕ ⊕○⊕ ○ ⊕○⊕ ⊕ ○⊕⊕ ○ ○⊕⊕ ⊕ ⊕⊕⊕ ○ ⊕⊕⊕ ⊕
4 3 => dp(4,2)=13 => 16-13 => 3 ○為反面 ⊕為正面 ○○○ ○ ˅ ○○○ ⊕ ⊕○○ ○ ⊕○○ ⊕ ○⊕○ ○ ○⊕○ ⊕ ⊕⊕○ ○ ⊕⊕○ ⊕ ○○⊕ ○ ○○⊕ ⊕ ⊕○⊕ ○ ⊕○⊕ ⊕ ○⊕⊕ ○ ○⊕⊕ ⊕ ⊕⊕⊕ ○ ⊕⊕⊕ ⊕
討論： 為什麼要逆向思考? dp的概念是把大問題切割成小問題，再由小問題推出大問題的解。 對於此題，若是逆向思考的話，只要考慮最後幾次是否符合答案要求；而以正向思考的話，小問題會有太多形式，還需多考慮到先前符合的情況在後來是否也符合。 簡單來說，先考慮所有情形再減去不符合的情形會比每次都要重新考慮有沒有後來才符合的情況要加入來的簡單。