概率DP主要用于求解期望、概率等题目。转移方程有时候比较灵活,没有固定的范式,没有模版可言。正如大部分的dp题目一样,思考量远大于代码量。需要注意的是,一般求概率是正推,求期望是逆推。
LightOJ 1030 Discovering Gold:
#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:
#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);
}
}
#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:
#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));
}
}
#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:
#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);
}
}