【ACM】概率DP

剖析

        先思考本次要解决的问题是什么，才能对症下药。找出问题的方法则是梳理，将整个过程有逻辑地复述一遍。
        概率DP的问题有两类：求期望、求概率。此外还会用到一个工具：高斯消元。同时有经典的“正向推概率，反向推期望”思想。
        先整理DP的特点：将问题分解成子问题，通过子问题的最优解求得父问题的最优解，实际上是对爆搜的剪枝。

期望DP

        对于求期望题，题解一般从后往前倒推。在飞行棋 一题中可以看出，正向逆向都可求解，但对于终点确定的问题，逆推要简单得多。其中原因是：从“起点到达该点的期望”的理解转变为“该点到达终点的期望”，相当于把主体从前导点转移到所求点（前者用 各个前导点的出现概率 * 转移概率*，后者用 *所求点出现概率 * 转移概率），省去了由于前导点出现概率不同导致的麻烦。【写到这里发现对期望的递推公式还是不理解】
        除了逆推求解思想，题解一般先求出状态转移方程，但我对于该方程一直理解不好。

---

示例：

PKU 3682: King Arthur’s Birthday Celebration

· 天数

· 花费

HDU 3853: LOOPS

---

HDU 4405: Aeroplane chess （上文提到的飞行棋）

正推

times[i] += ft(i-1,i) + ft(i-2,i) + ft(i-3,i) + ft(i-4,i) + ft(i-5,i) + ft(i-6,i);
ft(i,k) = (times[i] + list[i]) / 6;
(ft(i,k) / list[I] = (times[i] / list[i] + 1) / 6;)?
其中list[i]指到i点的概率，times[i]指到i点次数的期望。

逆推

times[i] = (times[i+1] + times[i+2] + times[i+3] + times[i+4] + times[i+5] + times[i+6]) / 6 + 1;
(times[i]/list[i] = (times[i+1] + times[i+2] + times[i+3] + times[i+4] + times[i+5] + times[i+6]) / list[i] / 6 + 1;)?

---

稍加总结(?)

/总结不出来…/

E(X) = ∑

概率DP

（待补充…）

---

他人博客：

正向推概率，反向推期望 - CSDN博客
期望&概率dp总结 - CSDN博客
ACM动态规划总结 - CSDN博客

---

题目目录：
PKU 3682: King Arthur’s Birthday Celebration
HDU 3853: LOOPS
HDU 4089: Activation
HDU 2262: Where is the canteen
HDU 3949: XOR
HDU 4418: Time travel
UVALive 5070: Awkward Lights