题目描述
你分别有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;
}