Gravatar
GDFRWMY
积分:318
提交:81 / 216
竟没一遍过,对不起党,对不起人民。。。

题目 111 [NOIP 2005]过河
2013-10-08 11:34:57
Gravatar
超级傲娇的AC酱
积分:646
提交:244 / 660
我在动归之前加了一个压缩处理,
若区间长度为S,T的公倍数,则易证区间的2个端点等效。
但压缩时应分类讨论,即不可压缩成2个石头相邻的情况。

Gravatar
老师好~~~
积分:136
提交:34 / 265
本题的路径压缩我是将大于s*t的都压缩到s*t,然后再DP.中间出现的错误有1.忘记压缩第一个石子与第二个石子之间距离,导致数据依旧很大,有些点还是E掉,就算将数组开大也会WA.2.不知道为什么S==T时路径压缩+DP一直WA,于是我改变策略枚举石子坐标然后模S,若为0则一定会走到这点然后计数器++,最后输出计数器return 0就好了.QAQ

Gravatar
老师好~~~
积分:136
提交:34 / 265
第一次交搜索果断跪了= =.........

题目 111 [NOIP 2005]过河
2013-08-08 20:07:08
Gravatar
cstdio
积分:4748
提交:1198 / 2108
采用了压缩t的倍数的算法,未整体移动理论上没问题但还是跪了(整体移动就可以)……求大神解释为什么会跪?

Gravatar
临轩听雨ゐ
积分:802
提交:247 / 483
用了一个叫题解的神器~ 将石子间距大[1,2,..,9,10]=2520的逐次减至小于2520.注意要在收尾增加0和l两个"石子" 520恰好是1, 2, ..., 10的最小公倍数。原理就是可以证明说状态函数的值肯定会出现大段的重复。在理论上可以保证的就是2520。 表示只想到了30%弱爆算法~

题目 111 [NOIP 2005]过河
2012-10-19 13:32:41
Gravatar
Truth.Cirno
积分:1591
提交:557 / 1253
(首先:那个速度很快的上榜的代码,即下面链接的代码是祝一凡大神写的代码,之后用我的号交的,本人代码与其无任何联系,是完全不如其算法的另一种较差的算法)
交了20多次,总算过了,
压缩用的是“较大冗余型”压缩,每次压缩距离为“10*最大跳跃距离”(压缩条件为:实际距离大于“20*最大跳跃距离”)。
用了一次随机化快排。
错的几次分别为:
未排序。
压缩时未实行“整体移动”。
未考虑0点到最小跳跃距离点,之间无法跳到的现实。
未考虑最小跳跃距离=最大跳跃距离的情况。(即:压缩时采取默认压缩距离为100——导致在“最小跳跃距离=最大跳跃距离”时程序结果出错)