ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC115 D - Christmas

再帰前計算動的計画法(DP)

問題
 提出コード
まずは、レベル $L$ バーガーをすべて食べたときの、食べる全体の枚数および食べるパティの枚数を求めます。
食べる全体の枚数を $a[L]$ とすると、
$a[L] = 2 \times a[L-1] + 3$
となります。
食べるパティの枚数を $p[L]$ とすると、
$p[L] = 2 \times p[L-1] + 1$
となります。
初期値は、 $a[0] = 1 , p[0] = 1$ です。
答えは、再帰によって求めることができます。
$solve(n,x) =$ レベル $n$ バーガーを、下から $x$ 層食べるときに食べることができるパティの枚数
とします。ここから先は場合分けをして求めます。

$n = 0$ のとき
$x=1$ なら答えは1、 $x=0$ なら答えは0です(問題の制約により、2以上になることはありません)。
上記を除き、 $x=1$ のとき
答えは0です。
$a[n] = x$ のとき
答えは $p[n]$ となります。
上記を除き、 $a[n]/2 + 1 \leqq x$ のとき
この式が意味するのは、レベル $n$ バーガーの半分を食べるかどうか、です。
必ずバーガーは奇数になるので、真ん中のパティの分が+1になっています。
このパターンでは、レベル $n-1$ バーガーを1つと、真ん中のパティを食べることが確定しているので、残りの部分だけ調べればよいです。
ということで、答えは $p[n-1] + 1 + solve(n-1,x - a[n]/2 - 1)$ となります。
それ以外、すなわち $a[n]/2 +1 \gt x$ のとき
一番下にあるバン1枚を食べたら、あとはレベル $n-1$ バーガーを食べる問題に帰着できます。
答えは $solve(n-1,x-1)$ です。

ということで、上のような再帰関数を作成すれば、答えを求めることができます。