题解：P1584 魔杖

· · 题解

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

dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+w_{}[i][j])

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