概率dp入门

概率dp

概率dp有两种题型,一种是求概率一种是求期望。

来结合一下题目

Aeroplane chess

题意

一个人在一条线上掷骰子,在线上有类似飞行棋的可以直接到达某个点的特殊点,问从$0$到$n$掷骰子次数的数学期望是多少?

题解

期望dp,dp最重要的就是从一个已知的最优状态转化到另一个最优状态。

为什么期望要反着求呢,因为你并不知道$dp[0]$这个点的值,因为我们定义$dp[x]$为$x$点到$n$点的掷骰子数的数学期望。而$dp[n]$的数学期望我们是知道的,是0,因为已经在$n$点了。之后我们倒推前面点的数学期望,因为你骰子是6面,从一个点可以到后面的六个点并且是等概率的,所以

$dp[i] = \sum_{j=i+1}^{i+6}dp[j]/6+1$

而且如果是特殊的飞行点,那么他的数学期望直接就是他的到的点的数学期望。

+2:没有从n-1开始,居然sb到从n开始计算。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 1e5 + 10;
double dp[maxn];
int nxt[maxn];
int main(){
#ifdef LOCAL
freopen("11.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m) && (m||n)){
rep(i,0,n+1) dp[i] = 0.0,nxt[i] = 0;
rep(i,0,m){
int x,y;scanf("%d%d",&x,&y);
nxt[x] = y;
}
per(i,0,n){
if(nxt[i]){
dp[i] = dp[nxt[i]];
}else{
double sum = 0.0;
rep(j,1,6+1){
if(i+j<=n){
sum+=dp[i+j];
}
}
dp[i] = sum/6.0+1.0;
}
}
printf("%0.4f\n",dp[0]);
}
return 0;
}

B - Discovering Gold

题意

跟上面的差不多,就是求期望。

题解

跟上面基本相似。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 110;
int T,n;
double dp[maxn];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d",&n);
rep(i,1,n+1) cin>>dp[i];
per(i,1,n){
double sum = 0.0;
double cnt = 0;
rep(j,i+1,i+7){
if(j<=n) sum+=dp[j],cnt++;
}
dp[i] += sum/cnt;
}
printf("Case %d: %0.9f\n",test_case,dp[1]);
}

return 0;
}