击败第 i 只怪物的额外加成只与“已击败数量对 10 取模”有关,而与具体击败了谁、击败了多少整十无关。因此可用动态规划,把“已击败数量 mod 10”作为状态,线性推进。
令 dp[m] 表示在处理完当前怪物之前,已击败数量 ≡ m (mod 10) 时能获得的最大经验值(滚动数组维护上一只怪物处理后的状态)。
小美会按照编号从小到大的顺序依次遇到 n 只怪物(编号为 1 ~ n),怪物 i(1≤i≤n) 的生命为 ai 。
对于每只怪物,小美都可以选择放走 Ta 或者击败 Ta。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册