• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

概率dp习题

互联网 diligentman 4个月前 (11-03) 42次浏览

概率

d

p

dp

dp习题

前言:太菜了,没学这个知识点,来补了,希望不咕咕咕。


1.D. Bag of mice

思路:板子题,求公主赢的概率,状态设为

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j]

i

i

i只白鼠,

j

j

j只黑鼠,公主先手赢得概率。
首先初始化:

d

p

[

i

]

[

0

]

=

1

,

d

p

[

0

]

[

j

]

=

0

,

i

[

1

,

w

]

,

j

[

0

,

b

]

dp[i][0]=1,dp[0][j]=0,iin[1,w],jin[0,b]

dp[i][0]=1,dp[0][j]=0,i[1,w],j[0,b]
然后状态转移:
分四种情况:
1.公主摸到白鼠,

d

p

[

i

]

[

j

]

+

=

i

i

+

j

dp[i][j]+=dfrac{i}{i+j}

dp[i][j]+=i+ji
2.公主摸到黑鼠,龙摸到白鼠,直接输了,不用加。
3.公主摸到黑鼠,龙摸到黑鼠,且跑出一个黑鼠。

d

p

[

i

]

[

j

]

+

=

j

i

+

j

×

j

1

i

+

j

1

×

j

2

i

+

j

2

×

d

p

[

i

]

[

j

3

]

dp[i][j]+=dfrac{j}{i+j}times dfrac{j-1}{i+j-1} times dfrac{j-2}{i+j-2}times dp[i][j-3]

dp[i][j]+=i+jj×i+j1j1×i+j2j2×dp[i][j3]
4.公主摸到黑鼠,龙摸到黑鼠,且跑出一个白鼠。

d

p

[

i

]

[

j

]

+

=

j

i

+

j

×

j

1

i

+

j

1

×

i

i

+

j

2

×

d

p

[

i

1

]

[

j

2

]

dp[i][j]+=dfrac{j}{i+j}times dfrac{j-1}{i+j-1} times dfrac{i}{i+j-2}times dp[i-1][j-2]

dp[i][j]+=i+jj×i+j1j1×i+j2i×dp[i1][j2]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int w,b;
double dp[N][N]; 
int main(){
	scanf("%d%d",&w,&b);
	for(int i=0;i<=w;i++) dp[i][0]=1;
	for(int i=0;i<=b;i++) dp[0][i]=0;
	for(int i=1;i<=w;i++)
		for(int j=1;j<=b;j++){
			dp[i][j]+=(double)i/(i+j);
			if(j>=3){
				dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
			}
			if(j>=2){
				dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]; 
			}
		}
	printf("%.9fn",dp[w][b]);
	return 0;
}


程序员灯塔
转载请注明原文链接:概率dp习题
喜欢 (0)