LYK 与实验室(lab)
Time Limit:5000ms Memory Limit:64MB
题目描述
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
输入样例 2
5 2 4 2
输出样例 2
2
输入样例 3
5 3 4 1
输出样例 3
0
数据范围
对于 20%的数据 n,k<=5。
对于 40%的数据 n,k<=10。
对于 60%的数据 n,k<=500。
对于 90%的数据 n,k<=2000。
对于 100%的数据 n,k<=5000。
1 #include<cstdio> 2 #define ll long long 3 using namespace std; 4 const int N=1e5+10; 5 const ll mod=1e9+7; 6 int n,a,b,k; 7 ll ans,f[N],sum[N]; 8 int main() { 9 scanf("%d%d%d%d",&n,&a,&b,&k); 10 f[a]=1; 11 for(int i=a; i<=n; i++) sum[i]=1; 12 for(int i=1; i<=k; i++) { 13 f[b]=0; 14 for(int j=1; j<b; j++) 15 f[j]=(sum[(j+b-1)/2]-sum[j]+sum[j-1]+mod)%mod; 16 for(int j=b+1; j<=n; j++) 17 f[j]=(sum[n]-sum[(j+b)/2]-sum[j]+sum[j-1]+mod)%mod; 18 for(int j=1; j<=n; j++) 19 sum[j]=(sum[j-1]+f[j])%mod; 20 } 21 for(int i=1; i<=n; i++) 22 ans=(ans+f[i])%mod; 23 printf("%d",(int)ans); 24 return 0; 25 }
思路：