Educational Codeforces Round 116 Arena Solution (Java/C++)

Solution:

Based on the size of the data, we can almost infer that the final complexity should be $n\cdot x$.

Therefore, we give this definition based on complexity: dp[i][j] represents the possible number of n live heroes remaining after a total of j points of damage have been dealt. Obviously dp[n][0]=1.

Obviously, assuming we have got the value of dp[x][y], then obviously the total damage next time is y+x-1 (if it exceeds x, it is directly counted as x. Because if the damage reaches x, all heroes must already be killed). The number of remaining heroes can range from 0 to x.
Let's assume that there are x' heroes left after the next attack. We can get: $$dp[x'][y+x-1]+=dp[x][y]\cdot C_x^{x'} \cdot (x-1)^{x-x'}$$This means that we choose x' people from x to survive, and among the x-x' people killed, the remaining HP can be arbitrarily chosen between 1 and x.

Code:

Java

Submission #133974506 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #133976065 - Codeforces
Codeforces. Programming competitions and contests, programming community
DigitalOcean Referral Badge 蜀ICP备19018968号