Educational Codeforces Round 116 Arena 题解 (Java/C++)

题解

根据数据规模，我们几乎可以推断最终的复杂度应该就是$n\cdot x$。

因此我们根据复杂度给出这样的定义：dp[i][j]表示总共打出j点伤害后剩下n个活着的英雄的可能数。显然dp[n][0]=1。

显然，假设我们已经得到dp[x][y]的值，那么显然下一次的总伤害为y+x-1（如果超出x就直接算作x即可。因为如果伤害达到x，所有英雄必然已经全部被杀了）。而剩下的英雄数目从0到x都有可能。
不妨设下一次攻击后剩下x'个英雄。我们可以得到$$dp[x'][y+x-1]+=dp[x][y]\cdot C_x^{x'} \cdot (x-1)^{x-x'}$$意思是说，我们从x中选择x'个人活下来，而被杀的x-x'个人中，其剩余的血量在1到x之间任意选择即可。

代码

Java

C++