期望dp学习：
类型1： 与图结合：
一般套路为dp[i]代表此时i到终点的期望，我们将图反向建立 并进行dp
1.例题：
P4316 绿豆蛙的归宿 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
考虑此时假设有一条i->j的边此时我们知道dp[j]的价值 可以发现dp[j]+e[i].dis 为这条边的期望
我们将其/k代表这条边的贡献
所以：
dp[i]=sum(dp[j]+e[i->j].dis)/k
至于遍历的顺序我们考虑拓扑就好了：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1e5 + 10;
double dp[maxn];
struct node
{
int to, next;
int dis;
}e[maxn<<1];
int head[maxn], cnt,in[maxn],degree[maxn];
void add(int u, int v, int dis)
{
e[++cnt].dis = dis;
e[cnt].next = head[u];
head[u] = cnt;
e[cnt].to = v;
}
queue<int>q;
void find()
{
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].next)
{
int y = e[i].to;
dp[y] += ((double)e[i].dis + dp[u]) / ((double)degree[y]);
in[y]--;
if (in[y] == 0)
q.push(y);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
in[x]++, degree[x]++;
add(y, x, z);
}
for (int i = 1; i <= n; i++)
{
if (in[i] == 0)
{
q.push(i);
}
}
find();
printf("%.2lf", dp[1]);
}
走路3 – 题目 – Daimayuan Online Judge
同类型的题目：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
int dp[maxn];
const int mod = 1e9 + 7;
int qpow1(int a, int b)
{
int res =1;
while (b)
{
if (b%2){
res = res * a%mod;
}
a = a*a%mod;
b >>= 1;
}
return res;
}
struct node
{
int to, next;
int dis;
}e[maxn << 1];
int head[maxn], cnt, in[maxn], degree[maxn];
void add(int u, int v, int dis)
{
e[++cnt].dis = dis;
e[cnt].next = head[u];
head[u] = cnt;
e[cnt].to = v;
}
queue<int>q;
void find()
{
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].next){
int y = e[i].to;
dp[y] +=(dp[u]+1)*qpow1(degree[y],mod-2)%mod;
dp[y] %= mod;
in[y]--;
if (in[y] == 0)
q.push(y);
}
}
}
signed main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
int z = 1;
cin >> x >> y;
in[x]++, degree[x]++;
add(y, x, z);
}
q.push(n);
find();
cout << dp[1];
}类型2：这类型的题目有个共同特点：现在有多少 剩下多少的情况到达终点要多少步
要注意的是我们要求转移时考虑我们此时的这一步
瓜子 – 题目 – Daimayuan Online Judge
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 2e3 + 10;
int dp[maxn][maxn<<1];//dp[i][j]代表此时还剩i个瓜子 且里面有j个瓜子壳到终点的步数
const int mod = 998244353;
int n;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
{
res = res * a%mod;
}
b >>= 1;
a = a * a%mod;
}
return res;
}
int sum1[maxn*3];
void init()
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 2 * (n - i); j++)//2*(n-i)代表此时最多的瓜子壳数量
{
int sum = i + j;
dp[i][j] = (j >= 1 ? dp[i][j - 1] * j%mod*sum1[sum]% mod : 0) + dp[i - 1][j + 2] * i%mod*sum1[sum]% mod+1;
}
}
}
signed main()
{
cin >> n;
for (int i = 1; i <= 3 * n; i++)
sum1[i] = qpow(i, mod - 2) % mod;
init();
cout << dp[n][0];
}
例题二：牛客2022的第一场一道题
期望的技巧：
算式：
1.
k*(p)^(k-1)=
(p^k)(求导)=1/(1-p)（当且仅当p<1）
技巧一：
Problem – 453A – Codeforces
我们假设考虑此时投掷到i的概率:p(x==i)
这个p(x==i)=p(x<=i)-p(x<=i-1)
运用此来计算：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
double qpow(double a, int b)
{
double res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
}
b >>= 1;
a = a * a;
}
return res;
}
signed main()
{
int n, m;
cin >> m >> n;
double ans = 0;
for (int i = 1; i <= m; i++)
{
ans += (i*((qpow((double)i / m, n)) - qpow((double)(i - 1) / m, n)));
}
printf("%.6lf", ans);
}类型3：如何处理dp[i][j]在转移的过程中会枚举到自己的问题?
I-你最爱的概率_2022广西师范大学暑期训练赛(重现赛) (nowcoder.com)
我们可以发现此时我们dp[i][j] 转移的话 右边也会出现dp[i][j]
处理方法：
其实我们只要将右边移项到左边就可以将dp[i][j]彻底分离开来了
习题练习：
1.kuangbin带你飞
1.
A Dangerous Maze – LightOJ 1027 – Virtual Judge (csgrandeur.cn)
其实这道题就有一系列概率dp的涉及到的东西：
dp[i]=….dp[i]
这个类型：
我们考虑对于这道题如何处理：
dp[i]代表此时从i门出去需要等待的时间：
对于正数:
dp[i]=a[i]
对于负数：
dp[i]=abs(a[i])+dp[0];
dp[0]=sum(dp[1]+dp[2]…dp[n])/n
我们将上述式子化简即可得到结果
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 9e6 + 10;
const int mod = 1e9 + 7;
int a[maxn];
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a%b);
}
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
int n;
cin >> n;
int sum = 0, num = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] < 0)
{
num++;
sum += abs(a[i]);
}
else
{
sum += a[i];
}
}
if (n-num == 0)
{
cout << "Case " << ++T << ": ";
cout << "inf" << endl;
continue;
}
int k = gcd(sum, n - num);
cout << "Case " << ++T << ": ";
cout << sum/k << '/' << (n - num)/k << endl;
}
}
Discovering Gold – LightOJ 1030 – Virtual Judge (csgrandeur.cn)
这道题是概率dp中很典型的例子：逆推：
我们设dp[i]代表此时从i点到n期望的分数：
考虑i可以到前面哪几个数 设这些数为n
dp[i]=sum(dp[i+1]+dp[i+2]+dp[i+3]..+dp[i+n])/n
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 110;
double dp[maxn];
double a[maxn];
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
dp[n] = a[n];
for (int i = n - 1; i >= 1; i--)
{
dp[i] = 0;
int cnt = min(1ll*6, n - i);
for (int j = 1; j <= cnt; j++)
{
dp[i] += (dp[i + j] + a[i]) / cnt;
}
}
cout << "Case " << ++T << ": ";
printf("%.6lf\n", dp[1]);
}
}
Race to 1 Again – LightOJ 1038 – Virtual Judge (csgrandeur.cn)
这道题可以看做期望dp的轮数问题
这类问题就是要加个1就好了：
我们预处理出所有数的约数：
dp[i]代表i到1 的次数
dp[i]=(dp[i1]+dp[i2]+….dp[in])/n+1:(n为约数个数)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int maxn = 1e5+10;
double dp[maxn];
double a[maxn];
vector<int>p[maxn];
void init()
{
for (int i = 1; i <= 1e5; i++)
{
for (int j = 1; j*i <= 1e5; j++)
{
p[i*j].push_back(i);
}
}
dp[0] = 0;
for (int i = 2; i <= 1e5; i++)
{
int len = p[i].size();
dp[i] = len;
for (auto x : p[i])
{
if (x == i)
continue;
dp[i] += dp[x];
}
dp[i] /= (len - 1);
}
}
signed main()
{
init();
int t;
cin >> t;
int T = 0;
while (t--)
{
int n;
cin >> n;
cout << "Case " << ++T << ": ";
printf("%.6lf\n", dp[n]);
}
}
Just another Robbery – LightOJ 1079 – Virtual Judge (csgrandeur.cn)
这道题与其所是概率dp更像是背包：
dp[i]代表我抢i元最大不被抓的概率
不被抓的概率就是所有不被抓的乘积
加下来就是背包模板了
/*
1.背包：
dp[i]代表在强到i元的最大不被抓概率
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 10010;
double dp[maxn];
int a[maxn];
double d[maxn];
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
memset(dp, 0, sizeof dp);
double maxx; int n;
cin >> maxx >> n;
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
cin >> a[i] >> d[i];
d[i] = 1 - d[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 10000; j >= a[i]; j--)
{
if (dp[j - a[i]])
{
dp[j] = max(dp[j], dp[j - a[i]] * d[i]);
}
}
}
maxx = 1 - maxx;
int ans = 0;
for (int i = 10000; i >= 0; i--)
{
if (dp[i]>=maxx)
{
ans = i;
break;
}
}
cout << "Case " << ++T << ": " << ans << endl;
}
}
Birthday Paradox – LightOJ 1104 – Virtual Judge (csgrandeur.cn)
这道题其实转化来就是：
Anx/ n^x<=1/2
由于此时我们可以发现当x不断增加的话 该式子不断减小 所以我们可以枚举其来处理该问题
至于不用二分的原因在于 A太大了 可能会导致错误
枚举可行的原因在于x一般比n小很多 案例就可以看出来
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
int n;
cin >> n;
int ans = 0;
double now = 1;
for (int i = 1; i <= n; i++)
{
now *= double(n - i) / n;
if (now <= 0.5)
{
ans=i;
break;
}
}
cout << "Case " << ++T << ": " << ans << endl;
}
}
Snakes and Ladders – LightOJ 1151 – Virtual Judge (csgrandeur.cn)
这道题是之前那道题的加强版 加强在于一般dp处理不了的问题 ：
就是我求dp[i] 会用到dp[j] 且dp[j]的求解过程 会用到dp[i]
这道题要利用到高斯消元不过我还没学 学完了再回来补题：
Dice (III) – LightOJ 1248 – Virtual Judge (csgrandeur.cn)
这道题我们可以利用dp[i]代表我看了i面的期望次数：
dp[i]=dp[i-1]*(i-1)/n+dp[i]*(n-i+1)/n+1;
化简一下就好：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
double dp[maxn];
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
int n;
cin >> n;
dp[n] = 0;
for (int i = n - 1; i >= 0; i--)
{
dp[i] = dp[i + 1] + double(n) / (n - i);
}
cout << "Case " << ++T << ": ";
printf("%.6lf\n", dp[0]);
}
}
Island of Survival – LightOJ 1265 – Virtual Judge (csgrandeur.cn)
这道就是比较典型的每次在两者之间选择的题目了
我们假设dp[i][j]代表此时还剩i个老虎 j个🦌 接下来就按他讲的转移就好了
dp[0][1-n]为1
要注意的是：
1、我们人也要算到其中：
2、对于情况4 我们要分别考虑并选择最大值
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e3 + 10;
double dp[maxn][maxn];
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
int a, b;
cin >> a >> b;
for (int i = 0; i <= b; i++)
{
dp[0][i] = 1;
}
for (int i = 1; i <= a; i++)
{
for (int j = 0; j <= b; j++)
{
double now = 0;
if (i >= 2)
{
now += (double(i*(i - 1)) / ((i + j + 1)*(i + j)))*dp[i - 2][j];
}
if (j >= 1)
{
now += double(2 * i*j) / ((i + j + 1)*(i + j))*dp[i][j - 1];
}
if (j >= 2)//代表此时可以抽到2只
{
double now1 = now, now2 = now;
now1 += double(2*j) / ((i + j + 1)*(i + j))*dp[i][j - 1];
dp[i][j] = now1 / (1 - (double(j*j - j) / ((i + j + 1)*(i + j))));
dp[i][j] = max(dp[i][j], now2 / double(1 - (double(j*j + j) / ((i + j + 1)*(i + j)))));
}
else if (j == 0)
{
dp[i][j] = now;
}
else
{
double now1 = now, now2 = now;
now1+=((double(2*j))/((i + j + 1)*(i + j)))*dp[i][j - 1];
dp[i][j] = now1;
dp[i][j] = max(dp[i][j], now2 / double(1 - double(2 * j) / ((i + j + 1)*(i + j))));
}
}
}
cout << "Case " << ++T << ": ";
printf("%.6lf\n", dp[a][b]);
}
}
Beating the Dataset – LightOJ 1274 – Virtual Judge (csgrandeur.cn)
这道题是期望dp的一个线性问题:
我们考虑dp[i][j][k]i代表此时是第i位置 j代表此时已经有了j个yes 且此时答案为k ：0代表对 1 代表错
我们要考虑逆序处理：原因在于我们此时k的答案决定了我们下一次是对还是错
dp[i][j][0]= (dp[i+1][j][1]+1)*(n-i-(YES-j))/(n-i)+dp[i+1][j+1][0]*(YES-j)/(n-i);
dp[i][j][1]同理：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
double dp[2][5100][2];
signed main()
{
int t;
cin >> t;
int T = 0;
while (t--)
{
int n, m;
cin >> n >> m;
int cnt0 = m-2*n, cnt1 = 3*n-m;//0代表此时正确 1代表此时错误
dp[n & 1][cnt0][1] = dp[n & 1][cnt0][0] = 0;
for (int i = n - 1; i >= 0; i--)
{
int ret = n - i,now=i&1,nxt=(i+1)&1;
memset(dp[now], 0, sizeof dp[now]);
for (int j = min(cnt0, i); j >=max(0ll,i-cnt1); j--)
{
double p1 = 1.0*(cnt0 - j) / ret, p2 = 1.0*(n - i - (cnt0 - j)) / ret;
dp[now][j][0] = dp[nxt][j + 1][0] * p1 + (dp[nxt][j][1] + 1)*p2;
dp[now][j][1] = (dp[nxt][j + 1][0] + 1)*p1 + dp[nxt][j][1] * p2;
}
}
cout << "Case " << ++T << ": ";
printf("%.6lf\n", dp[0][0][0]);
}
}