程序设计在线评测(Online Judge)


问题 1028. -- 2011市赛题:郭嘉的八卦阵

1028: 2011市赛题:郭嘉的八卦阵

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 0
[提交][状态][讨论版]

题目描述

「三国杀」是一个很流行的卡牌游戏,在游戏里,「郭嘉」是一个很厉害的英雄,他有如下两个技能:

天妒:在你的判定牌生效后,你可以立刻获得它

遗计:你每受到一点伤害,就能从牌堆里摸两张牌

简单的「三国杀」规则如下:

1.一开始郭嘉血量为上限X,0张手牌,装备着「八卦阵」

2.「郭嘉」每受到一点伤害,就会掉一点血,当他血量为0,就输了

3.「桃」可以让「郭嘉」恢复一点血

4.当别人对「郭嘉」打出「杀」的时候,郭嘉需要出一张「闪」,否则受到一点伤害(郭嘉有「闪」的话必须出「闪」)

5.装备「八卦阵」有如下功能:当自己需要出「闪」,可判定,若为红色花色,则等效于出了一张「闪」

6.判定说明:从牌堆中翻出一张牌,观察其花色

7.「桃」「闪」都是红色花色

8.牌堆中红色花色和黑色花色比例一样

9.假设牌堆中有无数张牌,「桃」1/p,「闪」1/q

10.为了化简题目,有如下和普通三国杀不同的规定:当郭嘉摸到「桃」,立刻使用(不能保留),即血量加1,但不能超过血量上限X;郭嘉手中最多拿Y「闪」,当超过上限Y,必须立刻丢弃

 

现在「张飞」拿着无数张「杀」和郭嘉单挑,问期望需要多少张「杀」才能打败郭嘉?

 

输入

测试数据第一行是一个整数T(0<T<=100),接下来有T组数据

每组数据一行,每行有四个数字X,Y(1<=X,Y<=10),p,q(4<=p,q<=10).

输出

每组测试数据输出一个数,表示打败郭嘉的期望牌数,保留两位小数.

样例输入

1
1 1 4 4
2 2 4 4

样例输出

3.00

提示

涉及算法:高斯消元

根据题目我们可以知道郭嘉有(X+1)*(Y+1)个状态,即当前血量为X(0~10),闪的数量为Y(0~10)

可以根据递推关系得到(X+1)*(Y+1)个未知数和方程,利用线性代数高斯消元求解

方程递推如下:

我们用E(x,y)表示当前血量为x,闪的数量为y 需要的期望杀数

那么:

当y != 0的时候

有1/2的概率八卦判定为黑色,需要出闪,即有1/2的概率到E(x,y-1)

有1/P的概率八卦判定为桃,血量+1,即有1/p的概率到E(x+1,y)

有1/Q的概率八卦判定为闪,闪+1,即有1/Q的概率到E(x,y+1)

有1-1/2-1/P-1/Q的概率八卦判定为红色但不是桃闪,即有1-1/2-1/P-1/Q的概率到E(x,y)

由于消耗了一张杀,所以我们就可以列以下方程:

E(x,y)= 1/2 * E(x,y-1)  + 

 1/P * E(x+1,y)  + 

 1/Q * (x,y+1) +

 (1-1/2-1/P-1/Q) * E(x,y)   +  

 1;(最后这个1表示消耗了一张杀)

同理,当y == 0的时候

我们可以得到以下方程:(和上边分析类似,就是更烦,涉及到遗技这个技能,就不详细说明了)

E(x,y)= 1/2 * {

 (1 - 1/P - 1/Q) * (1 - 1/P - 1/Q) * E(x-1,0) +

 1/Q * (1 - 1/P - 1/Q) * E(x-1,1) +

 1/Q * 1/Q * E(x-1,2) +

 1/P * (1 - 1/P - 1/Q) * E(x,0) +

 1/P * 1/Q * E(x,1) +

 1/P * 1/P * E(x+1,0)

 }  + 

 1/P * E(x+1,y)  + 

 1/Q * (x,y+1) +

 (1-1/2-1/P-1/Q) * E(x,y)   +   1;

把未知数们移到左边,常数1留在右边,用高斯消元解之,初始情况满血无闪E(X,0)就是最后答案


 


 


 

来源

[提交][状态][讨论版]