游戲 解題報告
簡要題意
兩個人輪流進行操作，一次操作有一個參數 \(S\)，其收益為 \(F(S)\)，其中 \(F(S)\) 有 \(\dfrac{1}{2^S}\) 的概率返回 \(2^{S-1}\)，其余情況返回 \(0\)。一個人如果得到 \(n\) 的收益，那么他就贏了。已知第一個人先手，第二個人只會進行參數為 \(1\) 的操作。請問當第一個人采取最優策略時，他的獲勝概率為多少。
分析
概率 dp 有一個很典型的 Trick：如果存在多個終止狀態，那么可以逆序轉移。
那么本題我們定義 \(f_{i,j}\) 表示第一個人的分數為 \(i\)，第二個人的分數為 \(j\)，且第一個人先手時，第一個人的勝率；類似地，我們有 \(g_{i,j}\) 表示第二個人先手的情況。
那么我們的初始狀態為 \(f_{n,x}=1,g_{x,n}=0(x\in [0,n-1])\)。
那么我們存在轉移：
\[\begin{aligned}
f_{i,j}&=\max_{\large 1 \le p,i+2^p \le n}\normalsize \dfrac{1}{2^p}\times g_{i+2^{p-1},j} +(1-\dfrac{1}{2^{p-1}})\times g_{i,j}\\
g_{i,j}&=\dfrac{f_{i,j}+f_{i,j+1}}{2}
\end{aligned}
\]
注意到 \(g_{i,j}\) 的值只和 \(f\) 有關，于是我們直接帶入進去。
然后就可以直接 dp 了。
浙公網安備 33010602011771號