\(f[s][i][j][k]\)表示还剩\(s\)次攻击,分别有\(i,j,k\)个血量为\(1,2,3\)的奴隶主时,期望受到伤害。
因为期望是倒推,所以这么表示从后往前求,注意\(a,b,c\)的更新顺序(全写反了QAQ)!顺推的话需要同时维护概率(概率就是伤害了)。
注意判断不能超过7。
命中每个的概率是\(i(j,k)/(i+j+k+1)\).
//1124kb 8ms
#include <cstdio>
double f[53][9][9][9];
void Init()
{
// f[0][A][B][C]=0;
for(int i=0; i<50; ++i)
for(int a=0; a<=7; ++a)
for(int b=0; b<=7-a; ++b)
for(int c=0; c<=7-a-b; ++c)
{
double p=1.0/(a+b+c+1.0);
f[i+1][a][b][c]+=/*1.0**/p*(f[i][a][b][c]+1.0);
if(a) f[i+1][a][b][c]+=(double)a*p*f[i][a-1][b][c];
if(b){
if(a+b+c<7) f[i+1][a][b][c]+=(double)b*p*f[i][a+1][b-1][c+1];
else f[i+1][a][b][c]+=(double)b*p*f[i][a+1][b-1][c];
}
if(c){
if(a+b+c<7) f[i+1][a][b][c]+=(double)c*p*f[i][a][b+1][c];
else f[i+1][a][b][c]+=(double)c*p*f[i][a][b+1][c-1];
}
}
}
int main()
{
Init();
int A,B,C,K,T; scanf("%d",&T);
while(T--)
scanf("%d%d%d%d",&K,&A,&B,&C),printf("%.2lf\n",f[K][A][B][C]);
return 0;
}
BZOJ.4832.[Lydsy1704月赛]抵制克苏恩(期望DP)的更多相关文章
-
BZOJ4832[Lydsy1704月赛]抵制克苏恩——期望DP
题目描述 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一个游戏,每个玩家拥有一个 30 点血量的 ...
-
【bzoj4832】[Lydsy1704月赛]抵制克苏恩 期望dp
Description 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一个游戏,每个玩家拥有一个 ...
-
BZOJ4832: [Lydsy1704月赛]抵制克苏恩(期望DP)
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 913 Solved: 363[Submit][Status][Discuss] Description ...
-
【期望dp】bzoj4832: [Lydsy1704月赛]抵制克苏恩
这个题面怎么这么歧义…… Description 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一 ...
-
【BZOJ 4832】 [Lydsy2017年4月月赛] 抵制克苏恩 期望概率dp
打记录的题打多了,忘了用开维记录信息了......我们用f[i][j][l][k]表示已经完成了i次攻击,随从3血剩j个,2血剩l个,1血剩k个,这样我们求出每个状态的概率,从而求出他们对答案的贡献并 ...
-
BZOJ4832: [Lydsy1704月赛]抵制克苏恩(记忆化&;期望)
Description 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一个游戏,每个玩家拥有一个 ...
-
BZOJ4832: [Lydsy1704月赛]抵制克苏恩 (记忆化搜索 + 概率DP)
题意:模拟克苏恩打奴隶战对对方英雄所造成的伤害 题解:因为昨(今)天才写过记忆化搜索 所以这个就是送经验了 1A还冲了个榜 但是我惊奇的发现我数组明明就比数据范围开小了啊??? #include &l ...
-
[bzoj4832][Lydsy1704月赛]抵制克苏恩
题目大意:有一个英雄和若干个所从,克苏恩会攻击$K$次,每次回随机攻击对方的一个人,造成$1$的伤害.现在对方有一名克苏恩,你有一些随从.如果克苏恩攻击了你的一名随从,若这名随从不死且你的随从数量不到 ...
-
【BZOJ 4832 】 4832: [Lydsy2017年4月月赛]抵制克苏恩 (期望DP)
4832: [Lydsy2017年4月月赛]抵制克苏恩 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 275 Solved: 87 Descripti ...
随机推荐
-
JavaScript中的this陷阱的最全收集
JavaScript来自一门健全的语言,所以你可能觉得JavaScript中的this和其他面向对象的语言如java的this一样,是指存储在实例属性中的值.事实并非如此,在JavaScript中,最 ...
-
记录对依赖注入的小小理解和autofac的简单封装
首先,我不是一个开发者,只是业余学习者.其次我的文化水平很低,写这个主要是记录一下当前对于这块的理解,因为对于一个低水平 的业余学习者来说,忘记是很平常的事,因为接触.应用的少,现在理解,可能过段时间 ...
-
linux之";server"; directive is not allowed here in
配置完rewrite之后重启nginx发现如下错误 "server" directive is not allowed here in* 原因是因为 外部配置的simple.con ...
-
原生js dom记忆的内容
1.DOM基础getElementByIdgetElementByTagNamegetElementByName getElementsByClass querySelector querySelec ...
-
GMM及EM算法
GMM及EM算法 标签(空格分隔): 机器学习 前言: EM(Exception Maximizition) -- 期望最大化算法,用于含有隐变量的概率模型参数的极大似然估计: GMM(Gaussia ...
-
Pitcher Rotation
题意: n个人m个对手给出每个人能战胜每个敌人的概率,现在有g个比赛,每个人赛完后要休息4天(可重复用),求能获得胜利的最大期望个数. 分析: 因为只有每个人5天就能用一次,所以对于每个人来说,只有得 ...
-
CDH5.5.1版HBase安装使用LZO压缩
1.安装 RHEL/CentOS/Oracle 5 Navigate to this link and save the file in the /etc/yum.repos.d/ dire ...
-
处理soapUI特殊返回报文 【原】
String message ="<?xml version=\"1.0\" encoding=\"UTF-8\"?>" + & ...
-
Linux动态库生成与使用指南
相关阅读: Linux静态库生成指南 Linux下动态库文件的文件名形如 libxxx.so,其中so是 Shared Object 的缩写,即可以共享的目标文件. 在链接动态库生成可执行文件时,并不 ...
-
oracle 表或视图不存在
导入导出时,会自动表名自动加上了““双引号需要将表名改一下就可以了 alter table "oldtablename" rename to newtableName;