noip2005 过河 的路径压缩问题在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧.在桥上有一些石子,青蛙很讨厌踩在这些石子上.由于桥的长度和青蛙一次跳过的距离都是正整
来源:学生作业帮助网 编辑:六六作业网 时间:2024/05/27 10:00:57
noip2005 过河 的路径压缩问题在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧.在桥上有一些石子,青蛙很讨厌踩在这些石子上.由于桥的长度和青蛙一次跳过的距离都是正整
noip2005 过河 的路径压缩问题
在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧.在桥上有一些石子,青蛙很讨厌踩在这些石子上.由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度).坐标为0的点表示桥的起点,坐标为L的点表示桥的终点.青蛙从桥的起点开始,不停的向终点方向跳跃.一次跳跃的距离是S到T之间的任意正整数(包括S,T).当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥.
题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置.你的任务是确定青蛙要想过河,最少需要踩到的石子数.
我想知道为什么两石头的距离超过100,则可压缩到100,谁能证明下,
noip2005 过河 的路径压缩问题在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧.在桥上有一些石子,青蛙很讨厌踩在这些石子上.由于桥的长度和青蛙一次跳过的距离都是正整
以前做过,我证明一下:好像ST最大值分别为10,那么我们尽量让ST不重合,也就是S=9,T=10,来看一下,下面是可以跳到的序列:
0,9,10,18,19,20,27,28,29,30,36,37,38,39,40 ……
90,91,92,93,94,95,96,97,98,99,100.
注意到在前面会有断开的区间,也就是状态不同,而81以后青蛙可以调到任何一个格,所以可以压缩到100.至于为什么不压缩到更低,是因为前面那些便于你理解,实际上是这个公式算的:lcm(max(T),max(T)-1)证明复杂从略.
[问题分析]
此题初看是一个典型的搜索题。从河的一侧到河的另一侧,要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。
如果搜索石子,方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划,以石子分阶段的一维动规,时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任...
全部展开
[问题分析]
此题初看是一个典型的搜索题。从河的一侧到河的另一侧,要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。
如果搜索石子,方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划,以石子分阶段的一维动规,时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律,而且会有后效性。
这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索,然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。[批注:号称一词已成为湖南OI本世纪流行词汇 ]
[题目实现]
先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧,中间最多只有100个石子。假设桥长为最大值(109),石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地),处理时把这些跳过,就只会有M次运算。关键是找出每一个可以跳过的“空长条”。
我们可以先把青蛙可以跳出的所有可能求出,然后就可以求出可以忽略的“空长条”。
[特殊算法]
a[i]:前i个坐标中石子最小个数,初始为第i个坐标的石子个数
b[i]:第i个石子坐标
动规
a[0]=0;
对n>=t
a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}
对s=
但由于n较大直接动规会超时。所以要将n压缩
查看坐标,可以发现,如果b[i]-b[i-1]>t,显然对于b[i-1]+t
收起
问题分析:
此题初看是一个典型的搜索题。从河的一侧到河的另一侧,要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。
如果搜索石子,方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划,以石子分阶段的一维动规,时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何...
全部展开
问题分析:
此题初看是一个典型的搜索题。从河的一侧到河的另一侧,要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。
如果搜索石子,方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划,以石子分阶段的一维动规,时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律,而且会有后效性。
这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索,然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。[批注:号称一词已成为湖南OI本世纪流行词汇
题目实现:
先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧,中间最多只有100个石子。假设桥长为最大值(109),石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地),处理时把这些跳过,就只会有M次运算。关键是找出每一个可以跳过的“空长条”。
我们可以先把青蛙可以跳出的所有可能求出,然后就可以求出可以忽略的“空长条”。
特殊算法:
a[i]:前i个坐标中石子最小个数,初始为第i个坐标的石子个数
b[i]:第i个石子坐标
动规
a[0]=0;
对n>=t
a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}
对s=
但由于n较大直接动规会超时。所以要将n压缩
查看坐标,可以发现,如果b[i]-b[i-1]>t,显然对于b[i-1]+t
收起
这是完整的题目吗?不像啊!