求noip2005第二题过河的解题报告

来源：百度知道 编辑：UC知道 时间：2024/06/20 15:04:25
网上的解题报告太少了，而且没看懂，
具体怎样才能把空长条缩短？
求详细解释

动态转移方程很简单，主要是状态压缩

如果两块石头A和B,AB的距离超过2520,则让B及其后的石头的位置每次减2520,直到AB的距离小于2520.（PS:2520为1-10的最小公倍数)
这样一来路径就能减小为260000以下.
然后DP每个点就OK了.也不用考虑S=T的情况.程序极短
几个注意点:
1.若最后一个石头的位置离终点很远,那么将终点位置提前,方法一样.
2.有些地方不能到达,则可以将其石头数顶为101,这样S=T也不会错.

其实如果不考虑s=t的话，两点大于100的可以压到100，甚至20，某人用压到10仅错了1组数据。。。