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
Submission #133974506 - Codeforces
Codeforces. Programming competitions and contests, programming community
C++
Submission #133976065 - Codeforces
Codeforces. Programming competitions and contests, programming community