パ研コンペティション3日目 E - 美しい和音

• 問題
• AC

$f(i, x) := A_1, ..., A_i$を使って作れる総和$x$の美しい和音の総数、とする。$f$の漸化式は$A_i$を使う/使わないの二択の和で$f(i, x) = f(i-1, x) + f(i-2, x-A_i)$と書ける。これでDPすれば部分点が取れる。

また、DPのほとんどの枝で不可能な状態の遷移をしていることに注目すると高速化できる。例えば、$A_1, ..., A_i$から作れる美しい和音の最大スコア$g(i)$がDPで求まるので、これを事前に求めておいて、$g(i)$が$x$より小さくなったら枝刈りしてよい。これで満点が取れた。

---

でも、計算量がよくわからない。