ZROI – 19普转提 – Day5 – T3 – 打游戏


【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)$,复杂度瓶颈竟然在排序上…

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇