【ZROI-19普转提-Day5-T3】 打游戏#

题意#

原题面地址：【普转提七联测 Day 2】打游戏 - Zhengrui Online Judge ↗

解法#

$\rm{subtask}$ $\rm{1}$#

对于 $20\%$ 的数据，魔法值为 $0$。

不能放技能，容易想到贪心：按照生命值升序排序，从左到右逐个击破。

时间复杂度 $\mathcal{O}(n\log n)$.

$\rm{subtask}$ $2$#

对于另 $10\%$ 的数据，魔法值为 $1$.

只能放一次技能。显然在第一回合中先放技能是最优的。

于是可以确定第一回合放技能，后面的所有回合按照 $\rm{subtask}$ $1$ 中的贪心策略模拟。

只需要枚举一下第一回合放哪个技能即可。

时间复杂度 $\mathcal{O}(n\log n)$.

$\rm{subtask}$ $\rm{3}$#

对于另 $10\%$ 的数据，$n\leq 1000$ 且魔法值 $\leq 18$.

注意到 $m$ 很小。与 $\rm{subtask}$ $\rm{2}$ 相同，显然把这 $18$ 次技能放在前 $18$ 个回合是最优的。于是可以 $2^{18}$ 暴力枚举前 $18$ 个回合的出技能状态，后面的回合按照 $\rm{subtask}$ $\rm{1}$ 的贪心策略暴力模拟即可。

时间复杂度 $\mathcal{O}(n\log n+n\cdot 2^m)$.

$\rm{subtask}$ $\rm{4}$#

对于另 $10\%$ 的数据，$n\leq 10^5$ 且魔法值 $\leq 18$.

与 $\rm{subtask}$ $\rm{3}$ 相比，$n$ 的值变大了。考虑用变量记录前 $18$ 回合中使用的群攻次数，重击直接在数组上修改。

时间复杂度 $\mathcal{O}(n\log n+2^m)$.

$\rm{subtask}$ $\rm{5}$#

对于另 $30\%$ 的数据，$n\leq 50$，$m\leq 100$.

考虑动态规划。

设 $\operatorname{DP}_{i, c, z, q}$ 表示当前有 $i$ 点魔法值，正在打第 $c$ 个怪物，当前用了 $z$ 次重击，$q$ 次群攻，从现在到结束的最少花费。从后往前转移。

根据定义，要求的答案就是 $\operatorname{DP}_{m, 1, 0, 0}$ 的值。

容易想到转移方法和初始化方法。

时间复杂度 $\mathcal{O}(n\log n+nm^2)$.

$\rm{subtask}$ $\rm{6}$#

对于 $100\%$ 的数据，$n\leq 10^5$，$m\leq 100$.

注意到 $m$ 的值很小，但非常不幸，对想到正解没有什么正面的帮助。

首先把部分分的贪心迁移过来。按照生命值升序一个一个打，并且要先把技能都用完。

考虑是否存在更强的贪心策略。

**如果魔法值没了：**按照生命值升序一个一个打。

**如果还有魔法值：**思考一下可以得到：

如果当前不止两个怪，出群攻一定不劣于出重击；

如果当前只剩两个怪，从小到大重击。

于是可以贪心地完成。

时间复杂度 $\mathcal{O}(n\log n)$，复杂度瓶颈竟然在排序上…