[bzoj4832][Lydsy1704月赛]抵制克苏恩

题目大意：有一个英雄和若干个所从，克苏恩会攻击$K$次，每次回随机攻击对方的一个人，造成$1$的伤害。现在对方有一名克苏恩，你有一些随从。如果克苏恩攻击了你的一名随从，若这名随从不死且你的随从数量不到$7$，这名随从会召唤一个拥有$3$点血的新随从（血量到$0$时会死亡）。已知克苏恩攻击次数，场上一血，二血，三血的随从数量，问英雄收到的伤害点数的期望。

题解：$f_{i,j,k,l}$表示还可以攻击$i$下，一血随从$j$个，二血随从$k$个，三血随从$l$个时英雄收到伤害的期望。

$$f_{i,j,k,l}=\frac{f_{i-1,j,k,l}+1+f_{i-1,j-1,k,l}\times j+f_{i-1,j+1,k-1,l+check}\times k+f_{i-1,j,k+1,l-1+check}\times l}{j+k+l+1}\\（check为求出场上随从个数，<7返回1，否则返回0）$$

卡点：1.看成了每个随从都会召唤随从

C++ Code：

#include <cstdio>

#include <cstring>

using namespace std;

int Tim, k, a, b, c;

double f[55][8][8][8];

bool v[55][8][8][8];

int check(int a, int b, int c) {

	int tmp = a + b + c;

	if (tmp < 7) return 1;

	return 0;

}

double dfs(int k, int a, int b, int c) {

	if (k <= 0) return 0;

	if (a < 0 || b < 0 || c < 0) return 0;

	if (v[k][a][b][c]) return f[k][a][b][c];

	double &ans = f[k][a][b][c];

	ans = dfs(k - 1, a, b, c) + 1;

	ans = ans + dfs(k - 1, a - 1, b, c) * a;

	ans = ans + dfs(k - 1, a + 1, b - 1, c + check(a, b, c)) * b;

	ans = ans + dfs(k - 1, a, b + 1, c - 1 + check(a, b, c)) * c;

	ans = ans / (a + b + c + 1);

	v[k][a][b][c] = true;

	return ans;

}

int main() {

	scanf("%d", &Tim);

	while (Tim--) {

		scanf("%d%d%d%d", &k, &a, &b, &c);

		printf("%.2lf\n", dfs(k, a, b, c));

	}

	return 0;

}

巴特西

[bzoj4832][Lydsy1704月赛]抵制克苏恩

最新文章

热门文章