NOIP 2005 - 过河

Author Avatar
Jimmy Zhang Nov 07, 2017
  • Read this article on other devices

题面

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

数据范围

1L1091 \le L \le 10^9

1ST101 \le S \le T \le 10

1M1001 \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[ij]+isStone[i]  minHopjmaxHop}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掉就穿女装……

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

优化特殊情况

我们注意到题目中给出的取值范围 1minHopmaxHop101 \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=Qpx + (p + 1)y = Q

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

px+(p+1)y=gcd(p,p+1)=1px + (p + 1)y = gcd(p, p + 1) = 1
一定存在整数解

那么显然,对于方程:

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

也就一定存在整数解咯。

我们不妨假设我们得到了一组整数解 x0x_0y0y_0。并且,我们假设 0x0p0 \leq x_0 \leq p

Qp(p+1)Q \geq p(p + 1) 时,将这组解带入原方程并变换,易得:

y0=Qpx0p+1Qp2p+1p(p+1)p2p+1=pp+10\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}

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


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

那么我们就可以得到路径压缩的办法:如果两石头间的距离大于 (maxHop1)maxHop(\text{maxHop} - 1) \cdot \text{maxHop},那么我们只需要把它们间的距离改成 (maxHop1)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;
    }
}

实现

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2017/11/07/noip-2005-river/