BZOJ.4832.[Lydsy1704月赛]抵制克苏恩(期望DP)

时间:2021-08-04 00:50:12

题目链接

\(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)的更多相关文章

  1. BZOJ4832&lbrack;Lydsy1704月赛&rsqb;抵制克苏恩——期望DP

    题目描述 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一个游戏,每个玩家拥有一个 30 点血量的 ...

  2. 【bzoj4832】&lbrack;Lydsy1704月赛&rsqb;抵制克苏恩 期望dp

    Description 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一个游戏,每个玩家拥有一个 ...

  3. BZOJ4832&colon; &lbrack;Lydsy1704月赛&rsqb;抵制克苏恩&lpar;期望DP&rpar;

    Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 913  Solved: 363[Submit][Status][Discuss] Description ...

  4. 【期望dp】bzoj4832&colon; &lbrack;Lydsy1704月赛&rsqb;抵制克苏恩

    这个题面怎么这么歧义…… Description 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一 ...

  5. 【BZOJ 4832】 &lbrack;Lydsy2017年4月月赛&rsqb; 抵制克苏恩 期望概率dp

    打记录的题打多了,忘了用开维记录信息了......我们用f[i][j][l][k]表示已经完成了i次攻击,随从3血剩j个,2血剩l个,1血剩k个,这样我们求出每个状态的概率,从而求出他们对答案的贡献并 ...

  6. BZOJ4832&colon; &lbrack;Lydsy1704月赛&rsqb;抵制克苏恩(记忆化&amp&semi;期望)

    Description 小Q同学现在沉迷炉石传说不能自拔.他发现一张名为克苏恩的牌很不公平.如果你不玩炉石传说,不必担心,小Q 同学会告诉你所有相关的细节.炉石传说是这样的一个游戏,每个玩家拥有一个 ...

  7. BZOJ4832&colon; &lbrack;Lydsy1704月赛&rsqb;抵制克苏恩 &lpar;记忆化搜索 &plus; 概率DP&rpar;

    题意:模拟克苏恩打奴隶战对对方英雄所造成的伤害 题解:因为昨(今)天才写过记忆化搜索 所以这个就是送经验了 1A还冲了个榜 但是我惊奇的发现我数组明明就比数据范围开小了啊??? #include &l ...

  8. &lbrack;bzoj4832&rsqb;&lbrack;Lydsy1704月赛&rsqb;抵制克苏恩

    题目大意:有一个英雄和若干个所从,克苏恩会攻击$K$次,每次回随机攻击对方的一个人,造成$1$的伤害.现在对方有一名克苏恩,你有一些随从.如果克苏恩攻击了你的一名随从,若这名随从不死且你的随从数量不到 ...

  9. 【BZOJ 4832 】 4832&colon; &lbrack;Lydsy2017年4月月赛&rsqb;抵制克苏恩 (期望DP)

    4832: [Lydsy2017年4月月赛]抵制克苏恩 Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 275  Solved: 87 Descripti ...

随机推荐

  1. JavaScript中的this陷阱的最全收集

    JavaScript来自一门健全的语言,所以你可能觉得JavaScript中的this和其他面向对象的语言如java的this一样,是指存储在实例属性中的值.事实并非如此,在JavaScript中,最 ...

  2. 记录对依赖注入的小小理解和autofac的简单封装

    首先,我不是一个开发者,只是业余学习者.其次我的文化水平很低,写这个主要是记录一下当前对于这块的理解,因为对于一个低水平 的业余学习者来说,忘记是很平常的事,因为接触.应用的少,现在理解,可能过段时间 ...

  3. linux之&quot&semi;server&quot&semi; directive is not allowed here in

    配置完rewrite之后重启nginx发现如下错误 "server" directive is not allowed here in* 原因是因为 外部配置的simple.con ...

  4. 原生js dom记忆的内容

    1.DOM基础getElementByIdgetElementByTagNamegetElementByName getElementsByClass querySelector querySelec ...

  5. GMM及EM算法

    GMM及EM算法 标签(空格分隔): 机器学习 前言: EM(Exception Maximizition) -- 期望最大化算法,用于含有隐变量的概率模型参数的极大似然估计: GMM(Gaussia ...

  6. Pitcher Rotation

    题意: n个人m个对手给出每个人能战胜每个敌人的概率,现在有g个比赛,每个人赛完后要休息4天(可重复用),求能获得胜利的最大期望个数. 分析: 因为只有每个人5天就能用一次,所以对于每个人来说,只有得 ...

  7. CDH5&period;5&period;1版HBase安装使用LZO压缩

    1.安装      RHEL/CentOS/Oracle 5 Navigate to this link and save the file in the /etc/yum.repos.d/ dire ...

  8. 处理soapUI特殊返回报文 【原】

    String message ="<?xml version=\"1.0\" encoding=\"UTF-8\"?>" + & ...

  9. Linux动态库生成与使用指南

    相关阅读: Linux静态库生成指南 Linux下动态库文件的文件名形如 libxxx.so,其中so是 Shared Object 的缩写,即可以共享的目标文件. 在链接动态库生成可执行文件时,并不 ...

  10. oracle 表或视图不存在

    导入导出时,会自动表名自动加上了““双引号需要将表名改一下就可以了 alter table "oldtablename" rename to newtableName;