B - ゲーム Editorial by Kiri8128
【考え方】
状態数が少ないので全状態を持つ DP ができます。
\(2\) 人の合計が決まっているゲームでは、自分と相手の差を持つと遷移が簡単になることがあります。
【解法】
\({\rm DP}[i][j]\): 左に \(i\) 個、右に \(j\) 個残っている状態から始めてお互い最善を尽くしたときの、(先手が得る価値)\(-\)(後手が得る価値)
とします。 \(\displaystyle\frac{DP[A][B] + \sum_{i=1}^{A} a_i + \sum_{j=1}^{B} b_j}{2}\) が求めるものです。
- \({\rm DP}[0][0] = 0\)
- \({\rm DP}[i][0] = a_{A+1-i} - {\rm DP}[i-1][j]\quad (i > 0)\)
- \({\rm DP}[0][j] = b_{B+1-j} - {\rm DP}[i][j-1]\quad (j > 0)\)
- \({\rm DP}[i][j] = \max(a_{A+1-i} - {\rm DP}[i-1][j], b_{B+1-j} - {\rm DP}[i][j-1])\quad (i,\ j > 0)\)
のような遷移が成立します。 \(i, j\) が小さい方から更新すれば全体で \(O(AB)\) でこの問題を解くことができます。
posted:
last update: