概率dp

概率DP/期望DP總結

概述 一般來說,概率DP找到正確的狀態定義後,轉移是比較容易想到的。但狀態一定是“可數”的,把有範圍的整數作為陣列下標。事實上,將問題直接作為狀態是最好的。如問“n人做XX事的期望次數”,則設計狀態為f[i]表示i個人做完事的期望。轉移一般是遞推,即從上一個狀態轉移得(填表)或轉移向下一個狀態(刷表 […]

有向圖或者無向圖概率dp

概要: 一般形成環的用高斯消元法求解。但是遞推公式只和少數變數相關,可以考慮分離出係數。 總結: (看完下面的例題再來看這部分) 1.這類題型一般可以先寫出原始公式然後分離出困難的變數,比如第二題的dp[1]dp[1] , dp[father[i]]dp[father[i]] , 都是很難處理的變數 […]

HDU 5602 Black Jack(概率DP)

Description 21點又名黑傑克(英文:Blackjack),起源於法國,已流傳到世界各地。 21點,是一種使用撲克牌玩的賭博遊戲。亦是唯一一種在賭埸中可以在概率中戰勝莊家的一種賭博遊戲。 ———來自好搜百科 我們定義21點的規則如下,和原始規則稍微不一樣。 牌點數如下: A 2 3 4 5 […]

tyvj1864 守衛者的挑戰【概率dp】

解題思路: 注意到輸贏與挑戰順序無關,所以我們可以先把能加的揹包加了,看是否夠裝得到的碎片即可。 所以設f[i][j][k]表示挑戰了i關,贏了j場,揹包剩餘容積為k的概率,注意到k最多為n就夠了,而照著先揹包後碎片的順序,只要k<0該狀態即停止轉移。 分輸贏轉移即可。 #include< […]

【JZOJ B組】【NOIP2013模擬】守衛者的挑戰

Description 開啟了黑魔法師Vani的大門,隊員們在迷宮般的路上漫無目的地搜尋著關押applepi的監獄的所在地。突然,眼前一道亮光閃過。“我,Nizem,是黑魔法聖殿的守衛者。如果你能通過我的挑戰,那麼你可以帶走黑魔法聖殿的地圖……”瞬間,隊員們被傳送到了一個擂臺上,最初身邊有一個容量為 […]