Difficulty: 3.5 / Easy Tag: - 首先有个朴素的 DP：dp[i]=min⁡j=stdp[i−j]+[i∈A]dp[i]=\min_{j=s}^t dp[i-j]+[i\in A]dp[i]=minj=st dp[i−j]+[i∈A]。 但是注意到如果石头间间隔很远，可以随便跳，前面的石头位置已经不影响后面怎么跳了。 这个距离大概是多少呢？ 根据小凯的疑惑，在 ab−a−b+1ab-a-b+1ab−a−b+1 及以后的数都可以用 ax+byax+byax+by 表示。所以如果 t−s≥1t-s\ge 1t−s≥1，且 [l,r][l,r][l,r] 没有石头，从 [l,r−s(s−1)][l,r-s(s-1)][l,r−s(s−1)] 间所有点都可以跳到 rrr。所以这个距离设置成 2s(s−1)+t2s(s-1)+t2s(s−1)+t 是完全够用的。 这样 DP 总长度就缩小到 O(ns2)O(ns^2)O(ns2) 了。复杂度为 O(ns3)O(ns^3)O(ns3)。 当然，你可以通过 (min⁡,+)(\min,+)(min,+) 矩阵乘法等方式求出距离为 1∼2s(s−1)+t1\sim 2s(s-1)+t1∼2s(s−1)+t 的 DP 长什么样，优化成 O(s5+ns2)O(s^5+ns^2)O(s5+ns2) 或 O(s3log⁡s+ns2log⁡s)O(s^3\log s+ns^2\log s)O(s3logs+ns2logs) 之类的。但 nnn 这么小，感觉也没啥必要优化。 注意特判 s=ts=ts=t 的情况。 时间复杂度：O(ns3)O(ns^3)O(ns3)。

显然是dp，空的地方就是随便走就行了，完全可以不用老老实实的去看，我们可以把路径压缩，更简单地说就是如果后面的一个石头与前面的一个石头距离太远，我们可以把后面一个石头推到前一个石头附近，至于这个量是多少呢，可以用1000。

首先这道题的状态转移方程十分好推，即: 但是这道题的数据却是1e9的，开数组肯定爆。 那么我们就想到了离散化。 即mod 2520–lcm(1,…,10)，因此从一个点出发，无论青蛙能跳的距离是多少，它一定可以到达距离2520处。所以在前方2520没有石头时，可以将当前点向后移2520或者将后面的点向前移2520。 AC代码