题解：P1584 魔杖

千万不要被题目的算法标签误解了，这道题是一道简单的 dp 题，但只用 dp 也会超时，超时的原因是每算一个 $dp_{i,j}$ 都要算一遍区间和，所以我们在 dp 的基础上使用前缀和进行优化。dp 转移方程如下（$dp_{i,j}$ 意义为起点不超过 $i$，终点不超过 $j$ 的所有魔杖魔力之和的最大值）。

再加上前缀和的优化，时间复杂度为 $O(n^2)$ 不会超时。最后，注意要开 long long 否则会 WA 两个点。