Game（code festival 2014 上海 [E]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

解法

• $\text{dp}[a,b,c] :=$ 攻略済ステージ数が $(a, b, c)$ である状態で 1st trial を開始するときの、最適戦略によるコスト。

として、これを $(a,b,c)$ 降順に計算していきます。
あるゲームにおける戦略は、挑戦するステージの 4 つ組高々 $3^4$ 通りです。
これら $3^4$ 通りすべてに対して、遷移先および確率（どの段階までクリア成功するかで $5$ 通り）を列挙して、自己ループを適切に処理すれば、dp テーブルが更新できます。

この解法では計算量は $O(N_1N_2N_3)$ ですが、定数倍に $3^4\cdot 5$ などがついているので TLE に対する猶予が少なくなっています。