概率DP—二刷

概率DP二刷，摸到了一些概率套路，解决了循环转移的一些基本方法。

这个博客上有很多题目，我是看着它过的一遍。

---

关于概率DP思考

求期望DP设状态的几种方法：

• 问什么设什么(最常见)
• 设从当前状态到结束状态的期望步数
• 设f[i][j]=拿了i个A物品，j个B物品期望

期望DP的状态方程设计：

• 一般如果设的“当前状态到结束状态的期望步数”，那会考虑下一步操作对当前的影响(参考下面『单人博弈』、『迷宫』)
• 一般如果设的是“到当前状态的期望步数”，会考虑转移到当前状态的方法，求他们转移过来的概率，让后乘上它们的期望(参考CF这题，后来我发现这题用第一种方法设计也是可以的，dp就是这样很多情况下都有多种状态设计方案)

难的DP题会需要求解多个期望值，然后再综合计算。(如『OSU! 3.0』，如『亚瑟王的庆典』(没做))

---

麻球繁殖

开始有n个麻球，每个麻球有$p_i$的概率产生$i(0\le i<m)$个新麻球，母体当天死。问那n个麻球第$k$天内死光的概率？

看懂题目其实并不难。要意识到这题很强的 “独立性” ，利用这个独立性，可以简化考虑问题。

老规矩，问什么设什么。f[i]=1个麻球第i天内死光的概率。答案就是$f[k{]}^n$。初始化有$f[0]=0,f[1]=p[0]$。

转移考虑额外假设第一天产生了几个麻球，然后利用f[i-1]扩展一下，就能到达第i天了。

因为产生的那j个是独立的，直接幂一下就ok了。转移方程：
$$f[i]=\sum _{j=0}^{m-1}{p}_j\ast f[i-1{]}^j$$

这个就是网上写的所谓的“全概率公式”，跟平时正常推没什么区别。就是注意一下这个$p_i$的和一定要是1，用专业的话说因为这是“完备事件组”。我看了半天没看懂别人的做法，以为是自己不懂全概率公式，后来才发现是被网上的简易题目描述骗了

！注意！下面的变量名与题意描述不完全一致。

#include
using namespace std;
const int N = 1010;

int n, l, m;
double p[N], f[N];

double qkpow(double a, int n)
{
	double ret = 1;
	while(n)
	{
		if(n & 1) ret = ret * a;
		a = a * a;
		n >>= 1;
	}
	return ret;
}

int main()
{
	cin >> n >> l >> m;
	for(int i = 0; i < n; i++) cin >> p[i];
	f[0] = 0;
	f[1] = p[0];
	for(int i = 2; i <= m; i++)
	{
		for(int j = 0; j < n; j++)
			f[i] += p[j] * qkpow(f[i - 1], j);
	}
	printf("%.8lf\n", qkpow(f[m], l));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

循环概率DP

循环转移的处理方法：

• 设出方程组，然后用高斯消元粗暴的解决
• 或者待定系数法，将常量合并(这个其实还是方法1)
• 如果形如这题的式子，那么可以从叶子往根处理，可以保证每步仅有一个未知量。($f[u]=a[u]f[fa]+b[u]f[0]+c[u]f[u]$)

单人博弈

有三个正多面体骰子，第i个有k[i]面。每次扔全部三个骰子，得到等同于它们的和的分数。如果三个骰子分别掷得a、b、c，则得分清零。求得分≥n时的期望次数。

问什么设什么。f[i]=得分为i时，使分数≥n的期望步数。考虑下一步操作后：
$$f[i]=\sum _{k}p[k]\cdot f[i+k]+p[0]\cdot f[0]+1$$
开始时有$f[n]=f[n+1]=\cdots =f[2\ast n]=0$

转移方程可以看成$f[i]=a[i]\cdot f[0]+b[i]$，是可以解出$a[i]$和$b[i]$的。

迷宫

给定一棵$n$个点的树，开始你在根节点，在结点$u$上时有$kill[u]$的概率去根节点，$escape[u]$的概率结束，剩下的概率随机到一个与$u$相邻的点。求结束时期望经过的边数。

同样问什么设什么。f[x] = 从x逃脱的期望步数。可以分根、叶子、非叶子来考虑状态转移方程。之所以要区分叶子和非叶子，是因为叶子的转移是简单的，未知数少。

DP转移方程考虑下一步操作。

对于叶子节点，有回到根节点，直接escape，回到父亲共计3种情况。
$$f[x]=kill[x]\ast f[0]+escape[x]\ast 0+(1-kill[x]-escape[x])\ast (f[fa[x]]+1)$$
对于非叶节点，有回根，escape，去邻近点的3中情况。去邻近点可以拆分成回父亲，去去儿子2种，所以总共可以看作4种情况。
$$f[x]=kill[x]\ast f[0]+escape[x]\ast 0+\frac{1-kill[x]-escape[x]}{deg[x]}\ast (f[fa[x]]+\sum _{y\in son[x]}f[y]+1)$$
可以看作$f[x]=a[x]\ast f[0]+b[x]\ast f[fa[x]]+c[x]$，$c[x]$对应的就是儿子那一块了。因为我们是从叶子往根求的，所以儿子信息是常数。