我第一眼看到这个题的时候，也会疑惑：

这题朴素时间复杂度是 $O(m^2)$ 其中 $m\leq10000$。

在2004年的时候，显然 HN 应该拿不出可以 1s 跑这么快的机子。

很多人和我一样都对此疑惑不解，并试图找到时间复杂度更优的解法（我稍微翻看了以前的讨论版，好像并没有人找出）。

不过稍加思索后发现这题其实考的是朴素$O(m^2)$ dp的优化。

在做了一定的优化后，速度飞快。最慢的点不过5ms。这在当时的机器上也肯定可以跑进1s。