概要

動的計画法を用いて解くことのできる典型的な問題の例です．
少し複雑ですが，状態を丁寧に整理して漸化式を導いてください．

問題原案：uni_kakurenbo

解説

動的計画法を用いて解くことができます．
その一例を紹介します．

$2$ 数列 $A, B$ はいずれも 0-based indexing とします．

• 定義

  • $\mathrm{DP_0}(i,j) \coloneqq ($先頭 $i+1$ 枚目までの裏返し方で，末尾に裏を向いたカードが $j$ 個連続するようなものの総数$)$
  • $\mathrm{DP_1}(i,j) \coloneqq ($先頭 $i$ 枚目までの裏返し方で，末尾に裏を向いたカードが $j$ 個連続するようなものスコアの総和$)$

• 初期状態：

  • $\mathrm{DP_0}(0,0) = \mathrm{DP_0}(0,1) = 1$
  • それ以外はすべて $0$．

• 遷移：

  • $\text{For} \;\,i \gets [\, 0, 1, \ldots, N\,):$
    • $\mathrm{DP_0}(i+1, 0) \gets \sum\, \{\, \mathrm{DP_0}(i,j) \mid 1 \leq j < k \,\}$　#任意の枚数裏が連続 → 表
    • $\mathrm{DP_1}(i+1, 0) \gets \sum\, \{\, \mathrm{DP_1}(i, j) \mid 1 \leq j < k \,\} + \mathrm{DP_0}(i,0) \cdot A_i$
    • $\text{For} \;\,j \gets [\, 1, 2, \ldots, K\,]:$
      • $\mathrm{DP_0}(i+1, j) \gets \mathrm{DP_0}(i, j-1)$　# $j-1$ 枚裏が連続 → $j$ 枚裏が連続
      • $\mathrm{DP_1}(i+1, j) \gets \mathrm{DP_1}(i, j-1) + \mathrm{DP_0}(i, j) \cdot B_i$

• 結果：

  • $\sum_k \,\mathrm{DP_1}(N, k)$

解説：uni_kakurenbo

実装例