竟没一遍过,对不起党,对不起人民。。。
题目 111 [NOIP 2005]过河
2013-10-08 11:34:57
|
|
我在动归之前加了一个压缩处理,
若区间长度为S,T的公倍数,则易证区间的2个端点等效。 但压缩时应分类讨论,即不可压缩成2个石头相邻的情况。 |
|
本题的路径压缩我是将大于s*t的都压缩到s*t,然后再DP.中间出现的错误有1.忘记压缩第一个石子与第二个石子之间距离,导致数据依旧很大,有些点还是E掉,就算将数组开大也会WA.2.不知道为什么S==T时路径压缩+DP一直WA,于是我改变策略枚举石子坐标然后模S,若为0则一定会走到这点然后计数器++,最后输出计数器return 0就好了.QAQ
|
|
第一次交搜索果断跪了= =.........
题目 111 [NOIP 2005]过河
2013-08-08 20:07:08
|
|
采用了压缩t的倍数的算法,未整体移动理论上没问题但还是跪了(整体移动就可以)……求大神解释为什么会跪?
|
|
用了一个叫题解的神器~ 将石子间距大[1,2,..,9,10]=2520的逐次减至小于2520.注意要在收尾增加0和l两个"石子" 520恰好是1, 2, ..., 10的最小公倍数。原理就是可以证明说状态函数的值肯定会出现大段的重复。在理论上可以保证的就是2520。 表示只想到了30%弱爆算法~
题目 111 [NOIP 2005]过河
2012-10-19 13:32:41
|
|
(首先:那个速度很快的上榜的代码,即下面链接的代码是祝一凡大神写的代码,之后用我的号交的,本人代码与其无任何联系,是完全不如其算法的另一种较差的算法)
交了20多次,总算过了, 压缩用的是“较大冗余型”压缩,每次压缩距离为“10*最大跳跃距离”(压缩条件为:实际距离大于“20*最大跳跃距离”)。 用了一次随机化快排。 错的几次分别为: 未排序。 压缩时未实行“整体移动”。 未考虑0点到最小跳跃距离点,之间无法跳到的现实。 未考虑最小跳跃距离=最大跳跃距离的情况。(即:压缩时采取默认压缩距离为100——导致在“最小跳跃距离=最大跳跃距离”时程序结果出错) |