P10074 [GDKOI2024 普及组] 刷野 III
pikiuk
·
·
题解
irris 的题解太厉害了，我来点不怎么厉害的。
考虑 m=1 的情况，两种极端策略是：
- 我抓住一个一直刀，直到死亡为止。
- 我刀死最小的小怪，如果某只小怪被刀了最小小怪血量次数刀没死，我就换下一只。
继续考虑 m=1 的情况，容易发现我可以在最开始钦定一下我刀死小怪的血量，然后最坏情况下血量大于他的小怪都要被试错他的血量刀数。
仔细思考一下，发现 m>1 也可以这么做，具体的，我们把 \{a_n\} 排序，考虑如果我们钦定了若干小怪 \{b_m\}，最后死亡的是 a_{b_{1\sim m}} 的时候我们最坏情况需要的代价。
不难发现根据之前的分析下标在 (b_k,b_{k+1}) 的小怪要被试错 a_{b_{k}} 刀，很容易依次设计状态：f(i,j) 表示当前考虑到 a_i，确定了 b_{1\sim j} 且 b_j=i 时最坏情况需要的代价。转移的时候枚举 b_{j-1} 转移，有：
f(i,j)=\min\{f(k,j-1)+(i-k)\times a_k\}
这个式子不难用斜率优化优化，时间复杂度 \mathcal{O}(n^2)。