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

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

【Lydsy1704月赛】抵制克苏恩

Time  Limit:  1  Sec\mathrm{Time\;Limit:\;1\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

输入包含多局游戏。
第一行包含一个整数T  (T<100)T\;(T<100)，表示游戏的局数。
每局游戏仅占一行，包含四个非负整数K,A,B,CK,A,B,C，表示克苏恩的攻击力是KK，你有AA个11点血量的奴隶主，BB个22点血量的奴隶主，CC个33点血量的奴隶主。
保证KK是小于5050的正数，A+B+C≤7A+B+C\le 7 。

Output

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

Sample Input

1
2
1
1 1 1 1

Sample Output

1
0.25

Source

鸣谢Tangjz提供试题

标签：概率DP

Solution

一目了然的期望DP\mathrm{DP}。
令f[i][a][b][c]f[i][a][b][c]表示攻击ii次，场上有血量为1,2,31,2,3的奴隶主各a,b,ca,b,c个，期望下受到的伤害。分类打哪个角色转移到f[i+1][a′][b′][c′]f[i+1][a'][b'][c']。最后的答案为f[n][A][B][C]f[n][A][B][C]。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}