思路概述

击败第 i 只怪物的额外加成只与“已击败数量对 10 取模”有关，而与具体击败了谁、击败了多少整十无关。因此可用动态规划，把“已击败数量 mod 10”作为状态，线性推进。

状态设计

令 dp[m] 表示在处理完当前怪物之前，已击败数量 ≡ m (mod 10) 时能获得的最大经验值（滚动数组维护上一只怪物处理后的状态）。

转移

题目内容

小美会按照编号从小到大的顺序依次遇到 $n$ 只怪物（编号为 $1$ ~ $n$），怪物 $i(1 ≤ i ≤ n)$ 的生命为 $a_i$ 。

对于每只怪物，小美都可以选择放走 Ta 或者击败 Ta。