BZOJ4832【Lydsy1704月赛】抵制克苏恩 <概率DP>

Problem

【Lydsy1704月赛】抵制克苏恩

Description

同学现在沉迷炉石传说不能自拔。他发现一张名为克苏恩的牌很不公平。
如果你不玩炉石传说，不必担心，同学会告诉你所有相关的细节。炉石传说是这样的一个游戏，每个玩家拥有一个点血量的英雄，并且可以用牌召唤至多个随从帮助玩家攻击对手，其中每个随从也拥有自己的血量和攻击力。
同学有很多次游戏失败都是因为对手使用了克苏恩这张牌，所以他想找到一些方法来抵御克苏恩。他去求助职业炉石传说玩家椎名真白，真白告诉他使用奴隶主这张牌就可以啦。
如果你不明白我上面在说什么，不必担心，同学会告诉你他想让你做什么。
现在同学会给出克苏恩的攻击力是，表示克苏恩会攻击次，每次会从对方场上的英雄和随从中随机选择一个并对其产生点伤害。
现在对方有一名克苏恩，你有一些奴隶主作为随从，每名奴隶主的血量是给定的。如果克苏恩攻击了你的一名奴隶主，那么这名奴隶主的血量会减少点，当其血量小于等于时会死亡，如果受到攻击后不死亡，并且你的随从数量没有达到，这名奴隶主会召唤一个拥有点血量的新奴隶主作为你的随从；如果克苏恩攻击了你的英雄，你的英雄会记录受到点伤害。你应该注意到了，每当克苏恩进行一次攻击，你场上的随从可能发生很大的变化。
同学为你假设了克苏恩的攻击力，你场上分别有点、点、点血量的奴隶主数量，你可以计算出你的英雄受到的总伤害的期望值是多少吗？

Input

输入包含多局游戏。
第一行包含一个整数，表示游戏的局数。
每局游戏仅占一行，包含四个非负整数，表示克苏恩的攻击力是，你有个点血量的奴隶主，个点血量的奴隶主，个点血量的奴隶主。
保证是小于的正数，。

Output

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

Sample Input

1
2

1
1 1 1 1

Sample Output

0.25

Source

鸣谢Tangjz提供试题

标签：概率DP

Solution

一目了然的期望。
令表示攻击次，场上有血量为的奴隶主各个，期望下受到的伤害。分类打哪个角色转移到。最后的答案为。

加强版：LOJ2325「清华集训2017」小Y和恐怖的奴隶主。

Code

#include <bits/stdc++.h>
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
dnt f[50][10][10][10];
void init() {
    for (int i = 0; i < 49; 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++) {
                    dnt p = 1.0/(a+b+c+1.0);
                    f[i+1][a][b][c] += (f[i][a][b][c]+1.0)*p;
                    if (a) f[i+1][a][b][c] += f[i][a-1][b][c]*a*p;
                    if (b && a+b+c < 7) f[i+1][a][b][c] += f[i][a+1][b-1][c+1]*b*p;
                    if (b && a+b+c >= 7) f[i+1][a][b][c] += f[i][a+1][b-1][c]*b*p;
                    if (c && a+b+c < 7) f[i+1][a][b][c] += f[i][a][b+1][c]*c*p;
                    if (c && a+b+c >= 7) f[i+1][a][b][c] += f[i][a][b+1][c-1]*c*p;
                }
}
int main() {
    int T; read(T), init();
    while (T--) {
        int n, a, b, c;
        read(n), read(a), read(b), read(c);
        printf("%.2lf\n", f[n][a][b][c]);
    }
    return 0;
}