CF1606E Solution
考虑 dp。
注意到这个题造成的伤害与剩余人数有关,每次消灭的人数又与剩余人的血量最大值有关:
设 \(dp_{i,j}\) 表示剩下 \(i\) 个人中血量最大值为 \(j\) 的方案数。
显然当 \(i-1>=j\) 时一次伤害就可以杀光所有人,于是这时 \(dp_{i,j}=j^i-(j-1)^i\)(只需让最大血量为 \(j\))。
当 \(i-1<j\) 时,一次伤害会杀掉一部分人,我们考虑枚举剩下的人数 \(k\),则此时
\[dp_{i,j}=\sum_{k=2}^idp_{k,j-i+1}\binom i k(i-1)^{i-k} \]其中乘上 \(\binom i k\) 表示从 \(i\) 个人中选出 \(k\) 个留下来,乘上 \((i-1)^{i-k}\) 表示死去的人血量值可以在 \([1,i-1]\) 中任取。
\(\mathcal O(n^2m)\) 直接计算即可。
标签:最大值,solution,血量,cf1606e,binom,dp From: https://www.cnblogs.com/iorit/p/18040127