状态表示:$f[a][b][c][d][x][y]$表示已经有的红桃、黑桃、方块、梅花的张数是$a、b、c、d$,小王表示 的是x花色,大王表示的y花色的期望(即形成这个情况平均需要抽多少张牌);用0~3表示四种花色,$x$表示小王代替的花色,$y$表示大王代替的花色,如果$x$或$y=4$,说明还没有抽到小王或大王。
状态转移:$f[a][b][c][d][x][y]$能转移到的状态取决于下一张牌,因此需要枚举下一张牌,即四个花色和两个王,枚举两个王时,还需要枚举王代替的花色,并取代替后的min。
$f[a][b][c][d][x][y] += \frac{13-a}{sum} * f[a+1][b][c][d][x][y] + \frac{13-b}{sum} * f[a][b + 1][c][d][x][y] $ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \frac{13-c}{sum} * f[a][b][c + 1][d][x][y] + \frac{13-d}{sum} * f[a][b][c][d + 1][x][y] $ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + min{\frac{1}{sum} * f[a][b][c][d][i][y]} + min{\frac{1}{sum} * f[a][b][c][d][x][i]}$
#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 &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 0;//全都达到要求,说明到达终点,终点到终点的期望距离显然为0
int sum = a + b + c + d + (x != 4) + (y != 4);
sum = 54 - sum;//剩下多少牌
if(sum <= 0) return INF;//牌用完了还是没有达到目标,返回无解
v = 1;//从一个点转移到另一个点需要翻开一张牌,因此f的初值需要加上1
if(a < 13) v += (13.0 - a) / sum * dp(a + 1 , b , c , d , x , y);//如果该花色的牌没有用完,就转移.
if(b < 13) v += (13.0 - b) / sum * dp(a , b + 1 , c , d , x , y);//抽到该花色的概率为(13.0 - a) / sum
if(c < 13) v += (13.0 - c) / sum * dp(a , b , c + 1 , d , x , y);
if(d < 13) v += (13.0 - d) / sum * dp(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 * dp(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 * dp(a , b , c , d , x , i));
v += t;
}
return v;
}
int main()
{
cin >> A >> B >> C >> D;
memset(f , -1 , sizeof f);//先将f数组初始化成不存在的数
double t = dp(0 , 0 , 0 , 0 , 4 , 4);
if(t > INF / 2) t = -1;
printf("%.3lf\n" , t);
return 0;
}
v = 1;的赋值和后面v多次+=不重合吗?
状态转移那里,为什么是 += 啊
看代码注释,dp()求的是从当前状态走到最终状态的最小距离,等号左边的状态离最终状态更远,因此需要加上它下一个状态到最终状态的距离
等号右边不是把所有情况都加上了嘛
难不成是 +=1
对呀,但是注意每种情况前面都有一个概率,代表每种情况出现的可能性。你可能对这个状态转移的方向不太理解,因为这题的方向跟其他题目不一样,这题是递归的形式,先计算离终点近的,然后反推到起点。
我指的是代码上面文字那里哎, 那里的 +=
对,一个意思,上面状态转移对应的就是dp()里的
全部达到要求的递归边界 为什么不是等于 而是大于等于呢
如果是大于 那么应该会有一个为负的期望 不是很明白
因为求的是期望,取出来的牌是不确定的,所以存在有的牌已经达到要求但是有的牌暂时未达到,例如在实际情况中存在红桃、方块、梅花已经达到要求,但是红桃没有达到要求,在抽取红桃的过程中会抽取到其他花色的牌,因此返回条件就是大于等于。