【bzoj2318】game with probability
題目
Description
Alice和Bob在玩一個遊戲。有n個石子在這裡，Alice和Bob輪流投擲硬幣，如果正面朝上，則從n個石子中取出一個石子，否則不做任何事。取到最後一顆石子的人勝利。Alice在投擲硬幣時有p的概率投擲出他想投的一面，同樣，Bob有q的概率投擲出他相投的一面。
現在Alice先手投擲硬幣，假設他們都想贏得遊戲，問你Alice勝利的概率為多少。
Input
第一行一個正整數t，表示數據組數。
對於每組數據，一行三個數n，p，q。
Output
對於每組數據輸出一行一個實數，表示Alice勝利的概率，保留6位小數。
題解
玄學概率dp
雖然網上已有不少題解，但有很多關鍵的地方沒講到，本題解加入了很多我自己的對一些問題的一些解答，更完整，詳細，嚴謹，覺得沒有完全懂，還有疑惑的可以來參考一下
設計狀態
$dp[i][0/1]$表示當前狀態為【在投硬幣前還剩i個石頭，且現在是Alice/Bob投硬幣】投完硬幣之後的勝率
初始狀態為$dp[0][1]=1$,即當前沒有石頭，且是bob投硬幣（即Alice是最後一個取石子的人，即贏家），此時勝率為1（已經贏了）
然後我們就從這裡一直倒推到$dp[n][0]$,即答案
轉移方程
題目有這樣一句話
Alice在投擲硬幣時有p的概率投擲出他想投的一面，同樣，Bob有q的概率投擲出他相投的一面
所以我們要分類討論當前玩家會希望取走石頭，還是維持原樣（至於最後選哪個，我們待會再講）
另請注意，玩家並不知道自己的p和q，所以不會出現Alice為了有更大的概率得到想要的結果而故意想相反的結果之類的問題
1.當前局面下，取走更好
$dp[i][0]=p*dp[i-1][1]+(1-p)*dp[i][1] $
$dp[i][1]=q*dp[i-1][0]+(1-q)*dp[i][0]$
以$dp[i][0]$的計算為例，前半部分是第一步Alice拿了，然後局面就變成了有$i-1$個石頭並且是後手，所以乘的是$dp[i-1][1]$
後半部分就是第一步Alice沒有拿，那就變成了有$i$個石頭並且是後手，所以是乘上$dp[i][1]$
但是這個轉移方程有交叉引用，但不用擔心，可以按如下方法處理（以dp[i][0]為例）
帶入$dp[i][1]$
$dp[i][0]=p*dp[i-1][1]+(1-p)*(q*dp[i-1][0]+(1-q)*dp[i][0]) $
拆括號，並將$(1-q)*dp[i][0]$移到左邊
$dp[i][0]-(1-p)*(1-q)*dp[i][0]=p*dp[i-1][1]+(1-p)*q*dp[i-1][0]$
將係數除過去
$dp[i][0]=(p*dp[i-1][1]+(1-p)*q*dp[i-1][0])/(1-(1-p)*(1-q))$
dp[i][1]同理
$dp[i][1]=(dp[i-1][0]*q+dp[i-1][1]*(1-q)*p)/(1-(1-p)*(1-q))$
2.當前局面下，不取更好
$dp[i][0]=(dp[i-1][1]*(1-p)+dp[i-1][0]*p)*(1-q))/(1-p*q)$
$dp[i][1]=(dp[i-1][0]*(1-q)+dp[i-1][1]*q)*(1-p))/(1-p*q)$
3.如何選擇
在當前剩下i個石頭的情況下，要到i-1顆石頭的狀態，無非就是Alice取了，或是Bob取了
若Alice取了，那麼接下來的勝率就是$dp[i-1][1]$,否則就是$dp[i-1][0]$
也就是說，我們只要比較這兩個勝率的大小，就可以決定Alice希望選哪個（這裡指的是希望選哪個）
那bob呢？
注意到若Bob取了，那麼接下來的勝率就是$dp[i-1][0]$,否則就是$dp[i-1][1]$
若alice 決定取，則$dp[i-1][1]>dp[i-1][0]$,那麼Bob肯定不取
也就是說，Alice和Bob的決策是相反的，那麼我們只要關注Alice選哪個即可
觀察1和2的公式，變化就是p和(1-p);q和(1-q)的位置互換了
我們可以用下面的代碼來完成這個過程
double p1=p,q1=q; if(dp[now][1]<dp[now][0]) p1=1-p,q1=1-q;
另外，通過打表可以發現，n到1000之後dp值基本沒有變過，即，我們只要算到1000就可以停了。
代碼
我是用滾動數組來實現的（雖然沒有必要）
代碼很短
#include<iostream>
#include<cstdio>
using namespace std;
double dp[2][2];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,now=0;
double p,q;
cin>>n>>p>>q;
dp[0][1]=1,dp[0][0]=0;
n=min(n,1000);
for(int i=1;i<=n;i++,now^=1)
{
double p1=p,q1=q;
if(dp[now][1]<dp[now][0]) p1=1-p,q1=1-q;
dp[now^1][0]=(dp[now][1]*p1+dp[now][0]*(1-p1)*q1)/(1-(1-p1)*(1-q1));
dp[now^1][1]=(dp[now][0]*q1+dp[now][1]*(1-q1)*p1)/(1-(1-p1)*(1-q1));
//cout<<dp[now][0]<<" "<<dp[now][1]<<endl;
}
printf("%.6f\n",dp[now][0]);
}
}
