概率dp学习记录
参考神仙blog：
概念
概率（期望）DP，就是一类结合概率论中求期望的动态规划问题，通常情况下的处理方式为倒推，即定义一个状态$dp[i]$为：已经到达$i$状态（根据题目自己定义），完成剩余要求所需要的期望步数，于是显然有$dp[n]=0$（如果$n$代表了最后一个状态），从而倒推求出$dp[0]$（或$dp[1]$之类的）
给出了一般方法，但由于动态规划没有模板一说，剩下就是多刷题了
习题
题意：
每张彩票上有一个漂亮图案，图案一共$n$种，如果你集齐了这$n$种图案就可以兑换大奖。现在请问，在理想（平均）情况下，你买多少张彩票才能获得大奖的？$n\le 33$
题解：
最经典的期望题，我们需要知道，如果买一次彩票能中$A$奖的概率为$\frac{b}{a}$，那么能中奖的期望购买彩票次数为$\frac{a}{b}$（取倒数即可），于是回到这题，定义状态$dp[i]$为：手上已有$i$种图案，兑换大奖还需要买的彩票数的期望，则答案为$dp[0]$，转移如下：
- 如果下一张彩票出的图案是已经有的：概率为$\frac{i}{n}$，$dp[i]=\frac{i}{n}(dp[i]+1)$
- 如果下一张彩票出的图案是新的：概率为$\frac{n-i}{n}$，$dp[i]=\frac{n-i}{n}(dp[i+1]+1)$
两者合并一下，得到：$dp[i]=\frac{i}{n}(dp[i]+1)+\frac{n-i}{n}(dp[i+1]+1)$
化简得：$dp[i]=dp[i+1]+\frac{n}{n-i}$
其实到这里就已经可以用动态规划A了这题，但我们再追求一下极致，从这个递推方程里推出一个公式来：
OK，很完美，接下来就是毒瘤的输出处理了，模拟通分+约分，然后输出格式处理一下就行了
code
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
33
34
35
36
37
38
39
40
41
42
43
44
45
| ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
int n;
int count(ll x){
int ans=0;
while(x){
ans++;
x/=10;
}
return ans;
}
int main(){
while(~scanf("%d",&n)){
ll ans1=1,ans2=1;
for(int i=2;i<=n;i++){
ll tp=lcm(i,ans2);
ll x1=tp/ans2,x2=tp/i;
ans2=tp;
ans1=ans1*x1+x2;
ll tp2=gcd(ans1,ans2);
ans1/=tp2,ans2/=tp2;
}
ans1*=n;
ll tp2=gcd(ans1,ans2);
ans1/=tp2,ans2/=tp2;
if(ans2==1){
printf("%lld\n",ans1);
continue;
}
ll dai=ans1/ans2;
if(dai) ans1%=ans2;
int numfen=max(count(ans1),count(ans2)),numdai=count(dai);
for(int i=0;i<=numdai;i++)
printf(" ");
printf("%lld\n%lld ",ans1,dai);
for(int i=0;i<numfen;i++)
printf("-");
printf("\n");
for(int i=0;i<=numdai;i++)
printf(" ");
printf("%lld\n",ans2);
}
return 0;
}
|
题意：
给一个DAG，起点为1，终点为n，每次绿豆蛙可以等概率地选择一条从这个节点出发的出边走过去，求从起点到终点的期望路径长度
题解：
设状态：$dp[i]$为已走到$i$节点，走完剩下节点所需要的期望路径长度，则转移方程为$dp[i]=\frac{1}{deg[i]}(\sum{(dp[v]+w)})$，其中$deg[i]$为$i$节点的出度，由于当前状态的转移用到了他的出边所连节点的转移，因此需要倒推，所以可以考虑反向建图然后跑一遍拓扑排序，在拓扑序上DP即可（其实大部分DAG上DP的题都需要拓扑排序，保证无后效性）
code
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
33
34
| int deg1[maxn],deg2[maxn];
double dp[maxn];
inline void toposort(){
queue<int> q;
q.push(n);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v,w=e[i].w;
dp[v]+=(dp[u]+1.0*w)/deg1[v];
if(deg2[v]){
deg2[v]--;
if(!deg2[v])
q.push(v);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
init_graph();
rep(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(y,x,z);
deg1[x]++,deg2[x]++;
}
toposort();
printf("%.2lf\n",dp[1]);
return 0;
}
|
重题：P1365 WJMZBMR打osu! / Easy
题意：
打OSU游戏（一种音游），会出现正确(O)和失误(X)两种情况，每N次正确的连击能获得$N^2$的分数加成，现在给你每次击打取得正确概率和N次击打，问最终获得的分数的期望
题解：
典型的高次期望问题，我们可以先考虑线性的问题：每N次正确的连击能获得N的分数加成，那么考虑状态$f[i]$表示达到第$i$次期望得分，则转移如下：
那么如果分数加成是平方次的呢？考虑状态$F[i]$表示这一状态，则转移如下：
为什么呢，因为$(x+1)^2-x^2=2x+1$，即：一个平方中+1所带来的分数加成为$2*线性加成+1$
code
| int n;
db p[maxn],f[maxn],F[maxn];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lf",&p[i]);
F[1]=f[1]=p[1]*1;
rep(i,2,n){
f[i]=(f[i-1]+1)*p[i];
F[i]=F[i-1]+p[i]*(2*f[i-1]+1);
}
printf("%.12lf\n",F[n]);
return 0;
}
|
题意：
跟上一道题一样，只是分数加成改为了$N^3$
题解：
那么转移方程对应改为：$Z[i]=Z[i-1]+pi$
code
| int n;
db p[maxn],f[maxn],F[maxn],z[maxn];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lf",&p[i]);
for(int i=1;i<=n;i++){
z[i]=z[i-1]+(3*f[i-1]+3*F[i-1]+1)*p[i];
F[i]=(F[i-1]+2*f[i-1]+1)*p[i];
f[i]=(f[i-1]+1)*p[i];
}
printf("%.1lf\n",z[n]);
return 0;
}
|
题意：
从起点到终点路上有N条河，需要坐船才能过，给出每条河的宽度和船速，走路速度恒为1，问从起点到终点的期望时间
题解：
对于过河来说，最慢的时间为$\frac{3L}{V}$（到达河边时船刚从河边离开，那么就需要等船跑完一个来回才能再乘坐），最快为$\frac{L}{V}$（到达河边时船刚好也到达，直接乘坐过去就行），又因为船速恒定，所以船出现在河内任何位置的的概率是相等的，即均匀分布，因此期望时间就是$\frac{\frac{3L}{V}+\frac{L}{V}}{2}=\frac{2L}{V}$，再加上走路的时间就是答案了
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int n,D;
int main(){
int cnt=0;
while(scanf("%d%d",&n,&D)){
if(n==0&&D==0) break;
double ans=0,zuo=0;
rep(i,1,n){
int p,L,v;
scanf("%d%d%d",&p,&L,&v);
ans+=2.0*L/v;
ans+=1.0*p-zuo;
zuo+=1.0*(p-zuo)+L;
}
ans+=1.0*D-zuo;
printf("Case %d: %.3lf\n\n",++cnt,ans);
}
return 0;
}
|
题意：
小明被困在一个洞穴里，他有个初始战斗力$f$，他每次有$N$条道路可选择（等概率随机选择），每条道路都有一个困难值$c_i$，如果他的战斗力大于所选通道的困难值，则他可以花费对应道路的天数$t_i$逃出洞穴，否则，他就只能花一天时间来使自己的战斗力增加对应道路的困难值的大小，问小明逃出洞穴的天数的期望
题解：
设状态$dp[i]$为小明战斗力为$i$时逃出洞穴的期望天数，则转移如下：
由于可能出现大于初始战斗力的情况，所以初始时选两到三倍战斗力开始转移
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int n,f,c[maxn],t[maxn];
double dp[maxn];
int main(){
while(~scanf("%d%d",&n,&f)){
memset(dp,0,sizeof(dp));
rep(i,1,n)
scanf("%d",&c[i]),
t[i]=floor((1.0+sqrt(5.0))/2.0*c[i]*c[i]);
for(int i=30000;i>=f;i--){
for(int j=1;j<=n;j++){
if(i>c[j]) dp[i]+=1.0*t[j]/n;
else dp[i]+=(1.0+1.0*dp[i+c[j]])/n;
}
}
printf("%.3lf\n",dp[f]);
}
return 0;
}
|
题意：
小明又被困住了，这次他被困在了一个$n*m$的矩阵中，初始他处于$(1,1)$（左上角），终点在$(n,m)$（右下角），每次他需要花费两点法力值然后在如下三种选择中选一种（给出三种选择的概率$p_1,p_2,p_3$，且保证$p_1+p_2+p_3=1$，且最右边一列的格子$p_2=0$，最下边一行的格子$p_1=0$）
- 往下走一格
- 往右走一个
- 原地不动
问小明到达终点的所花费法力值的期望
题解：
中规中矩的二维概率DP，考虑状态$dp[i][j]$为现在处在第$(i,j)$格子，到达终点的期望花费法力值，则转移为：
化简可得：
有一个坑点，就是这个式子分母不能为0（否则就浮点错误了），所以遇到$p_3=1$就跳过
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int n,m;
db p1[1015][1015],p2[1015][1015],p3[1015][1015];
db dp[1015][1015];
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,0,sizeof(dp));
rep(i,1,n){
rep(j,1,m){
scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);
}
}
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
if(fabs(p1[i][j]-1.0)<eps) continue;
dp[i][j]=(p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2.0)/(1.0-p1[i][j]);
}
}
printf("%.3lf\n",dp[1][1]);
}
return 0;
}
|
题意：
类似于优惠券那题，但难度有提高
有N中邮票，每次买到一种邮票的概率相等，为$\frac{1}{N}$，但是购买第$k$张邮票需要支付$k$元钱，问集齐所有N种邮票所需要花费的钱数的期望
题解：
如果是优惠券那题的题意，就是买一张邮票恒为1块钱，但现在变成了只要多买一张邮票，钱数就要+1，怎么办呢？不妨把需要买的张数和花钱数分开来考虑，先考虑怎么计算需要买的张数的期望，很简单，因为这就是优惠券那题$f[i]=f[i+1]+\frac{n}{n-i}$
现在来考虑钱数，由于买当前邮票所花的钱数还跟买当前邮票之前已经买了多少邮票（买的邮票张数）有关，因此转移应该为：
因而化简得到：
code
| int n;
db f[maxn],dp[maxn];
int main(){
scanf("%d",&n);
for(int i=n-1;i>=0;i--){
f[i]=f[i+1]+1.0*n/(n-i);
dp[i]=1.0*i/(n-i)*f[i]+dp[i+1]+f[i+1]+1.0*n/(n-i);
}
printf("%.2lf\n",dp[0]);
return 0;
}
|
题意：
村中有$1$个吸血鬼和$n-1$个村民，每天从这个$n$个里面随机选出两个，如果他俩是同类则无事发生，否则村民有$p$的概率会变成吸血鬼，问最后使得所有$n$个人都变为吸血鬼的天数的期望
题解：
经典的概率DP题，应该可以推公式，考虑定义状态$dp[i]$为现在有$i$个吸血鬼，把剩余人都变为吸血鬼的期望天数，则下一波选出的两个人为不同类的概率为：
因此转移方程为：
令
化简得到：
code
| int _,n;
db dp[maxn],p;
int main(){
for(scanf("%d",&_);_;_--){
memset(dp,0,sizeof(dp));
scanf("%d%lf",&n,&p);
for(int i=n-1;i>=1;i--){
db P=2.0*i*(n-i)/(n-1)/n*p;
dp[i]=(P*dp[i+1]+1.0)/P;
}
printf("%.3lf\n",dp[1]);
}
return 0;
}
|
题意：
小明被困在了一棵树中，初始时位于$1$号节点，每次随机选取与该节点相连的另一个节点走过去，有一定概率$k_i$掉入陷阱直接GG，有一定概率$e_i$被小红救走，求小明被救走之前所经过的边数的期望
题解：
首先我们可以根据题意定义出一个状态：$dp[i]$表示当前处在$i$号节点被救走所需要经过的边数的期望，则转移方程如下：
对于叶子节点：
对于非叶子节点：
其中，$m$为当前节点的度数
可以发现，一个状态不仅和他之后的状态有关，还和他之前的状态有关，那么这个问题就无法用DP解决了（因为DP的前提是无后效性），因此，到这一步还没完，还需要经过一系列的数学处理才能搞出一个无后效性的递推式，对于一个节点$i$，他的递推式可以写成 $dp[i]=A_i\cdot dp[1]+B_i\cdot dp[fa[i]]+C_i$ $(*)$
现在考虑将$dp[son[i]]转换一下$，设$i$的儿子点为$j$，则有：
代入到非叶子节点式子中，并化简，与$(*)$式作比较，得到三个系数如下：
而对于叶子节点，有：
可以发现，叶子节点的三个系数是可以直接得到的，那么我们可以从叶子节点出发，最终求得$A_1,C_1$，则答案为 $\frac{C_1}{1-A_1}$，显然当分母为$0$时无解
code
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| int _,n;
vector<int > E[maxn];
db k[maxn],e[maxn];
db a[maxn],b[maxn],c[maxn];
bool dfs(int u,int fa){
a[u]=k[u];
b[u]=(1-k[u]-e[u])/E[u].size();
c[u]=1-k[u]-e[u];
db tp=0;
for(int i=0;i<(int)E[u].size();i++){
int v=E[u][i];
if(v!=fa){
if(!dfs(v,u)) return false;
a[u]+=(1-k[u]-e[u])/E[u].size()*a[v];
c[u]+=(1-k[u]-e[u])/E[u].size()*c[v];
tp+=(1-k[u]-e[u])/E[u].size()*b[v];
}
}
if(fabs(1-tp)<eps) return false;
a[u]/=1-tp;
b[u]/=1-tp;
c[u]/=1-tp;
return true;
}
int main(){
int Ca=0;
for(scanf("%d",&_);_;_--){
rep(i,1,n) E[i].clear();
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%d",&n);
rep(i,1,n-1){
int x,y;
scanf("%d%d",&x,&y);
E[x].pb(y),E[y].pb(x);
}
rep(i,1,n){
scanf("%lf%lf",&k[i],&e[i]);
k[i]/=100,e[i]/=100;
}
printf("Case %d: ",++Ca);
if(dfs(1,-1)&&fabs(1-a[1])>eps) printf("%.12lf\n",c[1]/(1-a[1]));
else printf("impossible\n");
}
return 0;
}
|
题意：
有三枚骰子，面数分别为$k_1,k_2,k_3$，规定一个值$n$，初始答案为$Ans=0$，每次掷骰子三枚骰子同时掷，掷完后将骰子面朝上的权值和加入到答案中，此时如果出现了三枚骰子的点数分别为$a,b,c$，则回到$Ans=0$重新开始，如果$Ans>n$了就结束，问达到$Ans>n$所需掷骰子的次数的期望
题解：
其实是类似于上面那题，也属于转移方程有后效性需要数学推导的题型，这里定义状态为：$dp[i]$为$Ans=i$时完成任务所需要掷骰子的次数的期望，则转移方程如下：
其中，$p[0]$代表掷到三个骰子分别为$a,b,c$的概率，即$\frac{1}{k1k_2k_3}$，$p[k]$代表掷到骰子之和为$k$的概率，这些可以通过$O(k_1k_2k_3)$的预处理得到，下面考虑转化这个式子，令$dp[i]=A_idp[0]+B_i$，则$dp[i+k]=A{i+k}dp[0]+B_{i+k}$，代入上式，得到
于是得到：
最终答案为：$\frac{B_0}{1-A_0}$
code
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
33
34
35
36
37
| int _,n,k1,k2,k3,a,b,c;
double p[maxn],A[maxn],B[maxn];
void dfs(int i){
if(A[i]) return;
if(i>n){
A[i]=B[i]=0;
return;
}
A[i]=p[0],B[i]=1;
rep(k,3,k1+k2+k3){
dfs(i+k);
A[i]+=p[k]*A[i+k];
B[i]+=p[k]*B[i+k];
}
}
int main(){
for(scanf("%d",&_);_;_--){
memset(p,0,sizeof(p));
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
p[0]=1.0/(k1*k2*k3);
rep(i,1,k1){
rep(j,1,k2){
rep(k,1,k3){
if(i!=a||j!=b||k!=c)
p[i+j+k]+=p[0];
}
}
}
dfs(0);
printf("%.16lf\n",B[0]/(1-A[0]));
}
return 0;
}
|
题意：
袋子里有$w$只白鼠和$b$ 只黑鼠 ，$A$和$B$轮流从袋子里抓，谁先抓到白色谁就赢。$A$每次随机抓一只，$B$每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则$B$赢。$A$先抓，问$A$赢的概率。
题解：
状态$dp[i][j]$表示袋子里有$i$个白鼠和$j$黑鼠时$A$赢的概率，则分类讨论如下：
- A拿出白鼠，直接赢，概率：$\frac{i}{i+j}$
- A拿出黑鼠，B紧接着拿出白鼠，A赢概率为：0
两个人都拿出黑鼠，跑出来一个白鼠，A赢概率：$\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}\cdot dp[i-1][j-2]$
两个人都拿出黑鼠，跑出来一个黑鼠，A赢概率：$\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}\cdot dp[i][j-3]$
初始化：$dp[i][0]=1,dp[i][1]=\frac{i}{i+1}$，则答案为：$dp[w][b]$
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int w,b;
double dp[1005][1005];
int main(){
scanf("%d%d",&w,&b);
rep(i,1,w){
dp[i][0]=1;
dp[i][1]=i*1.0/(i+1);
}
for(int i=1;i<=w;i++){
for(int j=2;j<=b;j++){
dp[i][j]=i*1.0/(i+j)+j*1.0/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2];
if(j>2) dp[i][j]+=(j*1.0/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3]);
}
}
printf("%.9lf\n",dp[w][b]);
return 0;
}
|
题意：
有一个富豪，他决定每天撒钱，并且抛硬币，第一天1块钱，第二天3块钱，第三天5块，直到他抛到硬币向上的数量为K。求天数期望和钱期望。
题解：
类似于邮票收集那题，天数太简单了，$f[i]=f[i+1]+\frac{1}{p}$，对于钱数，增长是每次+2的，我们维护的$f[i]$代表天数，则$2f[i]-1$就是第$i$天花的钱，下一天如果硬币朝上，则需要花$2(f[i+1]+1)-1$的钱数，即$2f[i+1]+1$，常规递推即可
code
| int k;
db p,f[maxn],F[maxn];
int main(){
while(~scanf("%d",&k)&&k){
scanf("%lf",&p);
memset(f,0,sizeof(f));
memset(F,0,sizeof(F));
for(int i=k-1;i>=0;i--){
f[i]=f[i+1]+1/p;
F[i]=F[i+1]+2*f[i+1]+(2*(1-p)*f[i]+1.0)/p;
}
printf("%.3lf %.3lf\n",f[0],F[0]);
}
return 0;
}
|