华师一附中OI组

标题: 2761: LYK与实验室(lab) [打印本页]

作者: admin 时间: 2021-10-29 09:17
标题: 2761: LYK与实验室(lab)

题目描述

LYK在一幢大楼里，这幢大楼共有n层，LYK初始时在第a层上。

这幢大楼有一个秘密实验室，在第b层，这个实验室非常特别，对LYK具有约束作用，即若LYK当前处于x层，当它下一步想到达y层时，必须满足|x-y|<|x-b|，而且由于实验室是不对外开放的，电梯无法停留在第b层。

LYK想做一次旅行，即它想按k次电梯，它想知道不同的旅行方案个数有多少个。

两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。

输入格式(lab.in)

一行4个数，n,a,b,k。

输出格式(lab.out)

一个数表示答案，由于答案较大，将答案对1000000007取模后输出。

输入样例1

5 2 4 1

输出样例1

输入样例2

5 2 4 2

输出样例2

输入样例3

5 3 4 1

输出样例3

数据范围

对于20%的数据n,k<=5。

对于40%的数据n,k<=10。

对于60%的数据n,k<=500。

对于90%的数据n,k<=2000。

对于100%的数据n,k<=5000。

作者: admin 时间: 2021-10-29 09:19
各种神奇的电梯充斥着试卷，不知道他上辈子怎么了！
这个题第一感觉是建图后跑最短路径。先看看样例1,2吧，好像很有联系：
5层楼，LYK在2楼，不能去4楼，
按1次，2楼可以到1,3两层，不能去5楼，不满足条件|x-y|<|x-b|
所以2种可能。(2 1) (2 3)
第2次，1楼可以去2,3 3楼哪里都不能去。
所以(2 1 2) (2 1 3)种可能，
启发我们用广搜。但是好像也可以了类似最短路径DP。

作者: admin 时间: 2021-10-29 09:31
再看看这个式子：|x-y|<|x-b|，体现在图上是啥意思呢？x<>b，那么:当x>b，y只能取b-1到x+b-1范围
当x<b，y只能取b-x-1到b-1范围
好像有点像摆花那个题？连续推？

欢迎光临华师一附中OI组 (http://hsyit.cn/)