题面

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0,1,…,L0, 1, \dots, L （其中 LL 是桥的长度）。坐标为 00 的点表示桥的起点，坐标为 LL 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是 SS 到 TT 之间的任意正整数（包括 S,TS,T ）。当青蛙跳到或跳过坐标为 LL 的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 LL ，青蛙跳跃的距离范围 S,TS,T ，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

数据范围：

1≤L≤1091 \le L \le 10^9

1≤S≤T≤101 \le S \le T \le 10

1≤M≤1001 \le M \le 100

题目链接

分析

注：为了使得代码可读性更高，本人写的代码中变量名都使用了驼峰法命名。

bridgeLength\text{bridgeLength} ：独木桥的长度 LL

minHop\text{minHop} ：蛤一次跳跃的最短距离 SS

maxHop\text{maxHop} ：蛤一次跳跃的最长距离 TT

stoneNum\text{stoneNum} ：桥上石头个数 MM

转移方程

我们可以很容易写出状态转移方程：

dp[i]=min{dp[i],dp[i−j]+isStone[i] ∣ minHop≤j≤maxHop} dp[i] = min\{dp[i], dp[i - j] + \text{isStone}[i] \ | \ \text{minHop} \leq j \leq \text{maxHop}\}

简单地写出伪代码：

for (int i = 1; i <= bridgeLength; i++)
  for (int j = minHop; j <= maxHop && j <= i; j++)
    dp[i] = min(dp[i], dp[i - j] + isStone[i]);

注：其中 isStone[i]\text{isStone}[i] 代表第 ii 位置是否有石头，00 为没有，11 为有。

于是你瞬间兴奋了起来，大呼这道大水题不一次A掉就穿女装……

然后你默默地打开了淘宝……

优化特殊情况

我们注意到题目中给出的取值范围 1≤minHop≤maxHop≤101 \le \text{minHop} \leq \text{maxHop} \leq 10 ，也就是说，蛤的最短跳跃距离 minHop\text{minHop} 是可以等于最长跳跃距离 maxHop\text{maxHop} 的……

在这种情况下，蛤是没有选择的，只有一种跳法，即每次都跳 maxHop\text{maxHop} 那么长，遇到了石头…… 也只能踩上去。这种情况还用什么动态规划呢……

if (minHop == maxHop)
{
    int ans = 0;
    for (int i = 1; i <= stoneNum; i++)
        if (stone[i] % maxHop == 0)
            ans++;
    cout << ans << endl;
}

路径压缩

但特殊情况毕竟也是特殊情况，看看数据范围吧，要真开 10910^9 的数组不 MLE 也会 TLE。这个时候，我们就需要考虑路径压缩了。

再次观摩数据范围，我们发现，虽然桥可以长达 10910^9 ，但石头最多却只有区区 100100 个。也就是说，在该桥上石头是很稀疏的，存在大量的空白区域，而这些空白区域则是浪费时间的元凶。

但是我们首先也要注意，对于刚刚讲到的 minHop=maxHop\text{minHop} = \text{maxHop} 的情况由于步长固定，是不可以压缩的。

我们不妨假设青蛙一次跳跃的距离为 pp 或者 p+1p + 1 （均为整数），在经历了 xx 次距离为 pp 的跳跃和 yy 次距离为 p+1p + 1 的跳跃后移动的总距离为 QQ 。那么有：

px+(p+1)y=Q px + (p + 1)y = Q

我们知道，pp 和 p+1p + 1 的最大公约数 gcd(p,p+1)=1gcd (p, p + 1) = 1 ，所以由拓展欧几里得算法，很容易得知对于方程：

px+(p+1)y=gcd(p,p+1)=1 px + (p + 1)y = gcd(p, p + 1) = 1

一定存在整数解。

那么显然，对于方程：

px+(p+1)y=Q px + (p + 1)y = Q

也就一定存在整数解咯。

我们不妨假设我们得到了一组整数解 x0x_0 和 y0y_0 。并且，我们假设 0≤x0≤p0 \leq x_0 \leq p 。

当 Q≥p(p+1)Q \geq p(p + 1) 时，将这组解带入原方程并变换，易得：

y0=Q−px0p+1≥Q−p2p+1≥p(p+1)−p2p+1=pp+1≥0 \begin{aligned} & y_0 = \frac{Q - px_0}{p + 1} \\ & \geq \frac{Q - p^2}{p + 1} \\ & \geq \frac{p(p + 1) - p^2}{p + 1} \\ & = \frac{p}{p + 1} \geq 0 \end{aligned}

也就是说，当 Q≥p(p+1)Q \geq p(p + 1) 时，二元一次方程 px+(p+1)y=Qpx + (p + 1)y = Q 一定存在正整数解。

回到题目中来，上述的结论告诉我们，如果蛤每次走 maxHop−1\text{maxHop} - 1 或者 maxHop\text{maxHop} 步的话，一定可以走到 (maxHop−1)⋅maxHop(\text{maxHop} - 1) \cdot \text{maxHop} 以及之后的所有点。那么，到达这之后的所有点（下一个石头之前）所踩石头的最少数目都是一样的。我们自然也可以不用计算它们了。

那么我们就可以得到路径压缩的办法：如果两石头间的距离大于 (maxHop−1)⋅maxHop(\text{maxHop} - 1) \cdot \text{maxHop} ，那么我们只需要把它们间的距离改成 (maxHop−1)⋅maxHop(\text{maxHop} - 1) \cdot \text{maxHop} 就可以了。

sort(stone, stone + stoneNum + 1);

int k = maxHop * (maxHop - 1);
for (int i = 1, j = 0; i <= stoneNum; i++)
{
    stone[i] -= j;
    int delta = stone[i] - stone[i - 1];
    if (delta > k)
    {
        j += delta - k;
        stone[i] = stone[i - 1] + k;
    }
}

实现

完整参考代码

%%%