击败第 i 只怪物的额外加成只与“已击败数量对 10 取模”有关,而与具体击败了谁、击败了多少整十无关。因此可用动态规划,把“已击败数量 mod 10”作为状态,线性推进。
令 dp[m] 表示在处理完当前怪物之前,已击败数量 ≡ m (mod 10) 时能获得的最大经验值(滚动数组维护上一只怪物处理后的状态)。
dp[m]
≡ m (mod 10)
小美会按照编号从小到大的顺序依次遇到 nnn 只怪物(编号为 111 ~ nnn),怪物 i(1≤i≤n)i(1 ≤ i ≤ n)i(1≤i≤n) 的生命为 aia_iai 。
对于每只怪物,小美都可以选择放走 Ta 或者击败 Ta。
本题属于以下题库,请选择所需题库进行购买
ScanQRCodePrompt
请使用微信扫描下方二维码完成注册