《关于v初始化为1的原因》
先上代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double f[14][14][14][14][5][5], INF = 1e20;
int A, B, C, D;
double dfs(int a, int b, int c, int d, int x, int y)
{
if(a > 13 || b > 13 || c > 13 || d > 13) return INF;
double &v = f[a][b][c][d][x][y];
if(v >= 0) return v;
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 v = 0;
int sum = 54 - a - b - c - d - (x != 4) - (y != 4);
if(sum <= 0) return INF;
v = 1;
if(a < 13) v += (13 - a) * 1.0 / sum * dfs(a + 1, b, c, d, x, y);
if(b < 13) v += (13 - b) * 1.0 / sum * dfs(a, b + 1, c, d, x, y);
if(c < 13) v += (13 - c) * 1.0 / sum * dfs(a, b, c + 1, d, x, y);
if(d < 13) v += (13 - d) * 1.0 / sum * dfs(a, b, c, d + 1, x, y);
if(x == 4)
{
double t = INF;
for(int i = 0; i < 4; i++)
t = min(t, 1.0 / sum * dfs(a, b, c, d, i, y));
v += t;
}
if(y == 4)
{
double t = INF;
for(int i = 0; i < 4; i++)
t = min(t, 1.0 / sum * dfs(a, b, c, d, x, i));
v += t;
}
return v;
}
int main()
{
cin >> A >> B >> C >> D;
memset(f, -1, sizeof f);
dfs(0, 0, 0, 0, 4, 4);
if(f[0][0][0][0][4][4] > INF/2) puts("-1.000");
else printf("%.3lf\n", f[0][0][0][0][4][4]);
return 0;
}
这题思路还是逆推
f[i]: 从i卡牌状态到终点状态所需要的期望卡牌数
每次抽一张牌变到下个状态,所以每条路径的权值为1
$$ f[v] = p_1 \times (f[1] + 1) + p_2 \times (f[2] + 1) + p_3 \times (f[3] + 1) + … + p_k \times (f[k] + 1) \\ =\sum_{i=1}^{k}{p_i} + \sum_{i=1}^{k}{pi\times f[i]} \\ 因为v一定能到达下个局面,所以下个状态的概率和为1,这里的\sum_{i=1}^{k}{pi} = 1 \\ 那么就有:f[v] = 1 + \sum_{i=1}^{k}{pi\times f[i]} \\ 综上这里的f[v]可以初始化为1! $$
v = 1;是什么意思?
边的权值为1