【bzoj4832】[Lydsy2017年4月月赛]抵制克苏恩 概率期望dp

时间:2021-07-01 14:00:02

题目描述

你分别有a、b、c个血量为1、2、3的奴隶主,假设英雄血量无限,问:如果对面下出一个K点攻击力的克苏恩,你的英雄期望会受到到多少伤害。

输入

输入包含多局游戏。
第一行包含一个整数 T (T<100) ,表示游戏的局数。
每局游戏仅占一行,包含四个非负整数 K, A, B 和 C ,表示克苏恩的攻击力是 K ,你有 A 个 1 点血量的奴隶
主, B 个 2 点血量的奴隶主, C 个 3 点血量的奴隶主。
保证 K 是小于 50 的正数, A+B+C 不超过 7 。

输出

对于每局游戏,输出一个数字表示总伤害的期望值,保留两位小数。

样例输入

1
1 1 1 1

样例输出

0.25


题解

概率期望dp

一开始直接上了复杂度多了K的概率dp然后T死了。。。

由于期望具有可加性,因此不需要维护受到伤害为某值的各种情况,而是维护其期望值。

设$f[i][j][k][l]$表示前$i$次攻击,分别剩下$j$、$k$、$l$个血量为1、2、3的奴隶主时受到伤害的期望。那么直接考虑这次攻击的情况直接转移即可。

注意此时我们设的是总情况下的期望,因此在英雄受到伤害时期望值的增加应该为 概率*取值 ,取值为1,因此需要加上概率。所以再维护一个某情况的概率值即可。

时间复杂度$O(TK·8^3)$

注意千万不要把代码码错!(转移那里码错WA了无数次QAQ)

#include <cstdio>
#include <cstring>
double p[55][8][8][8] , f[55][8][8][8];
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
memset(p , 0 , sizeof(p)) , memset(f , 0 , sizeof(f));
int n , a , b , c , i , j , k , l;
double ans = 0;
scanf("%d%d%d%d" , &n , &a , &b , &c) , p[0][a][b][c] = 1;
for(i = 0 ; i < n ; i ++ )
{
for(j = 0 ; j <= 7 ; j ++ )
{
for(k = 0 ; k <= 7 ; k ++ )
{
for(l = 0 ; l <= 7 ; l ++ )
{
p[i + 1][j][k][l] += p[i][j][k][l] / (1 + j + k + l) , f[i + 1][j][k][l] += (f[i][j][k][l] + p[i][j][k][l]) / (1 + j + k + l);
if(j) p[i + 1][j - 1][k][l] += p[i][j][k][l] * j / (1 + j + k + l) , f[i + 1][j - 1][k][l] += f[i][j][k][l] * j / (1 + j + k + l);
if(k)
{
if(j + k + l == 7) p[i + 1][j + 1][k - 1][l] += p[i][j][k][l] * k / (1 + j + k + l) , f[i + 1][j + 1][k - 1][l] += f[i][j][k][l] * k / (1 + j + k + l);
else p[i + 1][j + 1][k - 1][l + 1] += p[i][j][k][l] * k / (1 + j + k + l) , f[i + 1][j + 1][k - 1][l + 1] += f[i][j][k][l] * k / (1 + j + k + l);
}
if(l)
{
if(j + k + l == 7) p[i + 1][j][k + 1][l - 1] += p[i][j][k][l] * l / (1 + j + k + l) , f[i + 1][j][k + 1][l - 1] += f[i][j][k][l] * l / (1 + j + k + l);
else p[i + 1][j][k + 1][l] += p[i][j][k][l] * l / (1 + j + k + l) , f[i + 1][j][k + 1][l] += f[i][j][k][l] * l / (1 + j + k + l);
}
}
}
}
}
for(i = 0 ; i <= 7 ; i ++ )
for(j = 0 ; j <= 7 ; j ++ )
for(k = 0 ; k <= 7 ; k ++ )
ans += f[n][i][j][k];
printf("%.2lf\n" , ans);
}
return 0;
}