概率dp专题整理(1/2)

Posted on | In

概率DP主要用于求解期望、概率等题目。转移方程有时候比较灵活，没有固定的范式，没有模版可言。正如大部分的dp题目一样，思考量远大于代码量。需要注意的是，一般求概率是正推，求期望是逆推。

LightOJ 1030 Discovering Gold:

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<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[104];
double dp[104];
int main(){
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++){
		int n;
		memset(dp, 0, sizeof dp);
		scanf("%d", &n);
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
		}
		dp[n] = a[n];
		for (int i = n-1; i >= 1; i--){
			int cnt = 0;
			for (int j = 1; j <= 6; j++){	
				if (i + j > n){
					break;
				}
				else{
					cnt++;
				}
				dp[i] += dp[i+j];
			}
			dp[i] =dp[i]/cnt+a[i];
		}
		printf("Case %d: %fn", t, dp[1]);
	}
}

LightOJ 1104 Birthday Paradox:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int n;
		scanf("%d", &n);
		double ans = 1.0;
		int k = 0;
		while (ans * 2 > 1){
			k++;
			ans = ans*(n - k) / n ;
		}
		printf("Case %d: %dn",i, k);
	}
}

LightOJ 1248 Dice (III):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	int t;
	scanf("%d", &t);
	for (int tt = 1; tt <= t; tt++){
		int n;
		scanf("%d", &n);
		double ans = 0;
		for (int i = 1; i <= n; i++){
			ans += 1.0*n / i;
		}
		printf("Case %d: %fn", tt,ans);

	}
}

LightOJ 1265 Island of Survival:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
double fun(int n){
	return n == 0 ? 1 : fun(n - 2)*(n - 1) / (n + 1);
}
int main(){
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++){
		int a, b;
		scanf("%d%d", &a, &b);
		printf("Case %d: %.7lfn", t, a & 1 ? 0 : fun(a));
	}
}

LightOJ 1038 Race to 1 Again:

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
double dp[100004];
double dfs(int n){
	if (fabs(dp[n] + 1) > 0.0000001)
		return dp[n];
	double ans = 0;
	int i, cnt = 2;
	for (i = 2; i*i < n; i++){
		if (n%i == 0){
			ans += dfs(i);
			ans += dfs(n / i);
			cnt += 2;
		}
	}
	if (i*i == n){
		ans += dfs(i);
		cnt++;
	}
	return dp[n] =( ans + cnt) / (cnt - 1);
}
int main(){
	int tt;
	scanf("%d", &tt);
	for (int i = 1; i <= 100000; i++){
		dp[i] = -1;
	}
	dp[1] = 0;
	for (int t = 1; t <= tt; t++){
		int n;
		scanf("%d", &n);
		printf("Case %d: %.7lfn", t, dfs(n));
	}
}

LightOJ 1079 Just another Robbery:

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
double dp[10004];
double risk[104];
int money[104];
int main(){
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++){
		memset(risk, 0, sizeof risk);
		memset(money, 0, sizeof money);
		double p;
		int n;
		scanf("%lf%d", &p, &n);
		for (int i = 1; i <= n; i++){
			scanf("%d%lf", &money[i], &risk[i]);
		}
		for (int i = 0; i <= 10000; i++)
			dp[i] = 1;
		dp[0] = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 10000; j >= 0; j--){
				if (j >= money[i]){
					dp[j] = min(dp[j], 1 - (1 - dp[j - money[i]])*(1 - risk[i]));
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= 10000; i++){
			if (dp[i] <= p){
				ans = max(ans, i);
			}
		}
		printf("Case %d: %dn", t, ans);
	}
}