动态规划求期望值的建模与应用
期望的线性性质与状态定义
在概率论中，期望具有线性性：对于随机变量 $X$ 和 $Y$，有 $E(aX + bY) = aE(X) + bE(Y)$。在动态规划中，该性质可用于构建状态转移方程。
状态定义通常为：从当前状态到达目标状态所需的期望操作次数。最终答案即为初始状态的期望值，而终止状态的期望为 0。
基础模型：图上期望路径
给定一个有向图，每个边有权值 $w$，从节点 $u$ 出发，每条出边被选中的概率均等。设 $f[u]$ 表示从 $u$ 到终点的期望代价。
状态转移公式：
$$ f[u] = \sum_{(u,v,w) \in E} \frac{w + f[v]}{\text{deg}(u)} $$其中 $\text{deg}(u)$ 是节点 $u$ 的出度。边界条件为 $f[\text{end}] = 0$。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2 * N;
double f[N];
int e[M], ne[M], w[M], h[N], idx;
int n, m, d[N];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
d[a]++;
}
double dp(int u) {
if (f[u] >= 0) return f[u];
f[u] = 0.0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
f[u] += (w[i] + dp(v)) / d[u];
}
return f[u];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
memset(f, -1, sizeof f);
printf("%.2lf\n", dp(1));
return 0;
}
扑克牌问题：带大小王的期望抽牌数
问题描述：一副 54 张牌（含大小王），要求收集至少 $A, B, C, D$ 张黑桃、红桃、梅花、方块。大小王可作为任意花色使用。
状态设计：$f[a][b][c][d][x][y]$ 表示已摸到 $a,b,c,d$ 张对应花色，大小王状态为 $x,y$（0~3 表示花色，4 表示未翻开）时，完成目标还需翻牌的期望次数。
状态转移考虑以下情况：
- 若所有花色达标，则 $f = 0$。
- 若剩余牌数不足，返回无穷大。
- 对每种未达上限的花色，计算其抽到的概率并递推。
- 大小王可选择最优花色，因此取最小期望。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 14;
const double INF = 1e20;
int A, B, C, D;
double f[N][N][N][N][5][5];
double dp(int a, int b, int c, int d, int x, int y) {
double &res = f[a][b][c][d][x][y];
if (res >= 0) return res;
int as = a + (x == 0) + (y == 0);
int bs = b + (x == 1) + (y == 1);
int cs = c + (x == 2) + (y == 2);
int ds = d + (x == 3) + (y == 3);
if (as >= A && bs >= B && cs >= C && ds >= D)
return res = 0.0;
int total = a + b + c + d + (x != 4) + (y != 4);
int remain = 54 - total;
if (remain <= 0) return res = INF;
res = 1.0; // 抽一张牌
if (a < 13) res += (13.0 - a) / remain * dp(a + 1, b, c, d, x, y);
if (b < 13) res += (13.0 - b) / remain * dp(a, b + 1, c, d, x, y);
if (c < 13) res += (13.0 - c) / remain * dp(a, b, c + 1, d, x, y);
if (d < 13) res += (13.0 - d) / remain * dp(a, b, c, d + 1, x, y);
if (x == 4) {
double min_val = INF;
for (int i = 0; i < 4; ++i)
min_val = min(min_val, 1.0 / remain * dp(a, b, c, d, i, y));
res += min_val;
}
if (y == 4) {
double min_val = INF;
for (int i = 0; i < 4; ++i)
min_val = min(min_val, 1.0 / remain * dp(a, b, c, d, x, i));
res += min_val;
}
return res;
}
int main() {
cin >> A >> B >> C >> D;
memset(f, -1, sizeof f);
double ans = dp(0, 0, 0, 0, 4, 4);
if (ans > INF / 2) ans = -1;
printf("%.3lf", ans);
return 0;
}
麻将七对问题：最优策略下的期望轮数
给定初始手牌，每次只能摸牌或弃牌，目标是达到"七对"（7 对相同牌）。
状态定义：$dp[i][j]$ 表示卡池中剩余 $i$ 张未摸牌，手中有 $j$ 张单张牌时，达成目标所需期望轮数。
关键点：
- 最优策略下，只会弃掉无法配对的牌。
- 摸牌后若能形成一对，则减少两张单牌；否则增加一张单牌。
- 概率计算：总牌数为 $i$，已有 $3j$ 张可配对的牌（因每对需两张），故摸到非配对牌的概率为 $(i - 3j)/i$，摸到可配对牌的概率为 $3j/i$。
状态转移：
$$ dp[i][j] = \frac{i - 3j}{i} \cdot (dp[i-1][j] + 1) + \frac{3j}{i} \cdot (dp[i-1][j-2] + 1) $$边界：当 $j = 0$ 时，已成胡，无需再摸。
#include <bits/stdc++.h>
using namespace std;
int t;
map<string, int> cnt;
long long dp[150][15];
const long long mod = 1e9 + 7;
long long ksm(long long x, long long y) {
long long ans = 1, tmp = x;
while (y) {
if (y & 1) ans = ans * tmp % mod;
y >>= 1;
tmp = tmp * tmp % mod;
}
return ans;
}
long long inv(long long x) {
return ksm(x, mod - 2);
}
int dfs(int i, int j) {
if (dp[i][j] != -1) return dp[i][j];
if (j == 0) return dp[i][j] = 0;
long long p1 = (i - 3 * j) * inv(i) % mod;
long long p2 = (3 * j) * inv(i) % mod;
if (j == 1) {
dp[i][j] = (p1 * (dfs(i - 1, j) + 1) % mod + p2 * 1 % mod) % mod;
} else {
dp[i][j] = (p1 * (dfs(i - 1, j) + 1) % mod + p2 * (dfs(i - 1, j - 2) + 1) % mod) % mod;
}
return dp[i][j];
}
int main() {
scanf("%d", &t);
memset(dp, -1, sizeof(dp));
int cas = 0;
while (t--) {
string s;
cin >> s;
cnt.clear();
for (int i = 0; i < 13; ++i) {
string card = s.substr(2 * i, 2);
cnt[card]++;
}
int singles = 0;
for (auto &it : cnt) {
if (it.second == 1) singles++;
}
cout << "Case #" << ++cas << ": " << dfs(123, singles) << endl;
}
return 0;
}
