思路 90pts 注意到 $O(n^2)$ 的暴力的能得到 90pts，不妨先考虑一下这个该怎么写。 我们可以考虑 dp，令 dp[i] 为到 i 的时候的最少的答案。 我们可考虑要从 dp[j] 扩展到 dp[i] 只有两种方法，第一种方法也就是在最后一次买东西的时候把羊毛都没买好，后面的直接走到目的地就行了。 第二种方法，就是在走到 j 后走回…