- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 42695
- 在线时间
- 小时
|
发表于 2021-9-16 14:16:50
|
显示全部楼层
现在我们再查看三步以内会变换到(b-1,b)而且最大值不小于3的状态的情况,只有
$(3b-1,b)\to(b,2b-1)\to(2b-1,b-1)\to(b-1,b)$
$(b-1,3b-2)\to(3b-2,2b-1)\to(2b-1,b-1)\to(b-1,b)$
$(5b-3,3b-2)\to(3b-2,2b-1)\to(2b-1,b-1)\to(b-1,b)$
其中$(5b-3,3b-2)\to(3b-2,2b-1)$已经至少减少2了,同样$(3b-2,2b-1)\to(2b-1,b-1)$在$b\ge3$时也至少减少2,都不会达到(b-1,b)状态就提前结束,可以不予讨论
而b=2时$(3b-2,2b-1)=(4,3)\to(3,1)\to(1,2)$,两轮到达(1,2)
同样(b-1,3b-2)出发时$b\ge 3$也提前终止,我们只需要考虑b=2的情况,对应$(1,4)\to(4,3)\to(3,1)\to(1,2)\to(2,1)\to(1,1)$是最大值为4时一个特殊的最长序列。
同样$(3b-1,b)\to(b,2b-1)$也提前终止。
所以实际上除了特例$(1,4)\to(4,3)\to(3,1)\to(1,2)\to(2,1)\to(1,1)$我们只需要再分析
$(b,2b-1)\to(2b-1,b-1)\to(b-1,b)$
$(2b-1,b-1)\to(b-1,b)$
这两种情况,它们都最多经过两步,而后面会继续跟上$(b-1,b)\to(b,1)\to(1,b-1)\to(b-1,b-2)\to(b-2,1)$,所以最多再经过四步后最大值减2,而且必然状态不是(b-1,b)形
所以我们得出除了特例$(1,4)\to(4,3)\to(3,1)\to(1,2)\to(2,1)\to(1,1)$(正好是最大值是4的另外一组最优结果,也只有最大值是4有两种最优结果)
那么最大值不小于3的任何初始状态,除了形如(b-1,b)的初始状态以外,要么三步内最大值减2,要么六步以内最大值减4.而且目的状态不是(b-1,b)形。
而(b-1,b)经过四步转化为(b-2,1),同样目的状态不是(b-1,b)形。
由此可以总结出3#提到的长度已经是最优的了。
|
|