概率dp专题

Happy Running（推公式）

画一个二维的坐标图，推公式即可。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        double k, x;
        scanf("%lf%lf", &k, &x);
        if(k == x) puts("0.50");
        else if(k < x) printf("%.2f\n", 0.5 * (x * x - k * k) / (x * x) + 0.5);
        else if(x >= k - x) printf("%.2f\n", 0.5 * pow(2 * x - k, 2) / (x * x));
        else puts("0.00");
    }
	return 0;
}

恶意竞争（期望dp）

期望dp入门题

概率dp一般是设已经算了多少的情况下，剩余的期望。这样的话结果就是0，然后递推到初始状态。方程可能会原地踏步，自己推自己，这个时候就需要移项。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e3 + 10;
double dp[N][N];
int n, s;
 
int main()
{
    scanf("%d%d", &n, &s);
    for(int i = n; i >= 0; i--)         //逆推到0
        for(int j = s; j >= 0; j--)
        {
            if(i == n && j == s) continue;   //注意这里，不加的话会除以0
            double a = 1.0 * i / n, b = 1.0 * j / s;
            dp[i][j] = 1 / (1 - a * b) * (a * b + (1 - a) * b * (1 + dp[i + 1][j])
                        + a * (1 - b) * (1 + dp[i][j + 1]) + 
                        (1 - a) * (1 - b) * (1 + dp[i + 1][j + 1]));
        }
    printf("%.10f\n", dp[0][0]);
    
	return 0;
}

带富翁（期望dp）

期望dp一般倒推比较好想，正推也行，但会比较复杂。倒推指的是从当前状态到结束状态的期望，而不是像其他dp那样从初始状态到当前状态的期望

dp[i]表示从i位置走到n位置的期望分数

那么dp[n] = a[n]

dp[i] = a[i] + dp[j] / len

j是所有能达到的点，len是能到达的点的个数

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e2 + 10;
double dp[N], a[N];
int n;
 
int main()
{
    scanf("%d", &n);
    _for(i, 1, n) scanf("%lf", &a[i]);
 
    dp[n] = a[n];
    for(int i = n - 1; i >= 1; i--)
    {
        dp[i] = a[i];
        int len = min(i + 6, n) - i;
        _for(j, i + 1, i + len)
            dp[i] += dp[j] / len;
    }
    printf("%.10f\n", dp[1]);
    
	return 0;
}

筛子游戏（期望dp+处理f[0]）

这题的难点在于dp方程里面有一个f[0]，这个f[0]是我们所求的，也是一个常数

处理的技巧就是设f[i] = A[i]f[0] + B[i],代入dp方程，得到A和B的递推式子

注意题目求的是大于n的,也就是f[n+1]=0,所以要从A[n],B[n]开始求。

递推求得A[0],B[0],由f[0] = A[0]f[0] + B[0]解出f[0]即可。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 600;
int n, a, b, c, k1, k2, k3, K;
double p[20], A[N], B[N];
 
int main()
{
    scanf("%d%d%d%d%d%d%d", &n, &k1, &k2, &k3, &a, &b, &c);
    _for(i, 1, k1)
        _for(j, 1, k2)
            _for(k, 1, k3)
            {
                if(i == a && j == b && k == c) p[0]++;
                else p[i + j + k]++;
            }
    K = k1 + k2 + k3;
    _for(i, 0, K) p[i] /= k1 * k2 * k3;
 
    for(int i = n; i >= 0; i--)
    {
        A[i] = p[0];
        B[i] = 1;
        _for(k, 1, K) 
        {
            A[i] += A[i + k] * p[k];
            B[i] += B[i + k] * p[k];
        }
    }
    printf("%.10f\n", B[0] / (1 - A[0]));
    
	return 0;
}

Balls（概率dp）

概率dp正推，期望dp逆推。这题先算概率，其实手推就可以发现是1+n/2了，因为每次期望增加是0.5。用概率dp的话，可以dp[i][j]表示i个黑球，j个白球的概率，然后由dp[i][j]更新dp[i+1][j]和dp[i][j + 1]即可。算出概率后枚举白球个数算期望，也可以得出答案就是1+n/2

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
int main()
{
    int n; scanf("%d", &n);
    printf("%.7f\n", 1 + n * 0.5);
    
	return 0;
}

珂学送分（期望dp）

同样倒推，用dp[i]表示以i为起点所能得到的期望，这样dp[n] = 1

然后枚举当前的分段即可,可以预处理加速。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e5 + 10;
int a[N], n, m, x, p[N], mx;
double dp[N], s[N];
 
int main()
{
    scanf("%d%d", &n, &m);
    _for(i, 1, n) scanf("%d", &a[i]), mx = max(mx, a[i]);
    while(m--)
    {
        scanf("%d", &x);
        if(x < mx)
        {
            puts("YNOI is good OI!");
            continue;
        }
 
        int sum = 0, r = 0;
        _for(l, 1, n)
        {
            while(r + 1 <= n && sum + a[r + 1] <= x) r++, sum += a[r];
            p[l] = r;
            sum -= a[l];
        }
 
        s[n + 1] = s[n + 2] = 0;
        s[n] = dp[n] = 1;
        for(int i = n - 1; i >= 1; i--)
        {
            int l = i, r = p[i];
            dp[i] = 1 + 1.0 / (r - l + 1) * (s[l + 1] - s[r + 2]);
            s[i] = s[i + 1] + dp[i];
        }
        printf("%.2f\n", dp[1]);
    }
    
	return 0;
}

P5104 红包发红包（期望）

手推一下，发现是一直除以2

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int mod = 1e9 + 7;
ll w, n, k;
 
ll binpow(ll a, ll b)
{
    ll res = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
 
ll inv(ll x) { return binpow(x, mod - 2); }
 
int main()
{
    scanf("%lld%lld%lld", &w, &n, &k);
    printf("%lld\n", w * inv(binpow(2, k)) % mod);
    
	return 0;
}

P6154 游走（期望）

这题不算是期望dp，用期望的定义可知答案就是所有路径的长度之和除以所有路径条数

dp一下即可

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 998244353;
ll dp[N], cnt[N];
vector<int> g[N];
int d[N], n, m;
 
ll binpow(ll a, ll b)
{
    ll res = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
 
ll inv(ll x) { return binpow(x, mod - 2); }
 
int main()
{
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        d[v]++;
    }
 
    queue<int> q;
    _for(i, 1, n) 
    {
        cnt[i] = 1;
        if(!d[i]) q.push(i);
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int v: g[u])
        {
            cnt[v] = (cnt[v] + cnt[u]) % mod;
            dp[v] = (dp[v] + dp[u] + cnt[u]) % mod;
            if(--d[v] == 0) q.push(v);
        }
    }
 
    ll a = 0, b = 0;
    _for(i, 1, n)
    {
        a = (a + dp[i]) % mod;
        b = (b + cnt[i]) % mod;
    }
    printf("%lld\n", a * inv(b) % mod);
    
	return 0;
}

P1297 [国家集训队]单选错位（期望）

计算每道题对答案的贡献即可

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e7 + 10;
int a[N], n, A, B, C;
 
int main()
{
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
    for (int i = 2; i <= n; i++)
        a[i] = ((long long) a[i - 1] * A + B) % 100000001;
    for (int i = 1; i <= n; i++)
        a[i] = a[i] % C + 1;
 
    double ans = 0;
    _for(i, 1, n)
    {
        int j = (i == n) ? 1 : i + 1;
        ans += 1.0 * min(a[i], a[j]) / (1LL * a[i] * a[j]);
    }
    printf("%.3f\n", ans);
    
	return 0;
}

SP1026 FAVDICE - Favorite Dice（期望dp）

dp[i]表示从已经出现i种面时，还需要扔色子的次数，dp[n] = 0, dp[0]即是答案

注意写方程时注意当前这次操作需要1次，不要漏写1

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e3 + 10;
double dp[N];
int n;
 
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        dp[n] = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            double a = 1.0 * i / n;
            dp[i] = a / (1 - a) + 1 + dp[i + 1];
        }
        printf("%.2f\n", dp[0]);
    }
	return 0;
}

P4316 绿豆蛙的归宿（期望dp）

这题直接暴力搜出所有的路径竟然不会T，能过

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
vector<pair<int, int>> g[N];
double dp[N], ans;
int n, m;
 
void dfs(int u, int fa, ll sum, double p)
{
    if(u == n) ans += sum * p;
    for(auto x: g[u])
    {
        int v = x.first, w = x.second;
        if(v == fa) continue;
        dfs(v, u, sum + w, p / g[u].size());
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
    }
 
    dfs(1, 0, 0, 1);
    printf("%.2f\n", ans);
   
	return 0;
}

当然，正解同样是逆推，用dp[u]表示从u到n的期望

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e5 + 10;
vector<pair<int, int>> g[N];
double dp[N], ans;
int d[N], n, m;
 
int main()
{
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
        d[v]++;
    }
 
    queue<int> q;
    vector<int> topo;
    _for(i, 1, n)
        if(!d[i])
            q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for(auto x: g[u])
            if(--d[x.first] == 0)
                q.push(x.first);
    }
 
    for(int i = topo.size() - 1; i >= 0; i--)
    {
        int u = topo[i];
        for(auto x: g[u])
        {
            int v = x.first, w = x.second;
            dp[u] += 1.0 / g[u].size() * (w + dp[v]);
        }
    }
    printf("%.2f\n", dp[1]);
   
	return 0;
}