题意：给定n个楼层，初始在a层，b层不可停留，每次选一个楼层x，当|x-now| < |x-b| 且 x != now 时可达（now表示当前位置），此时记录下x到序列中，走k步，最后问有多少种可能的数的序列.
解法：
定义： dp[i][j] 表示第i步在j楼的不同序列的个数
转移方程： 当j<b时， 那么dp[i][j] += dp[i-1][0~(j与b的中点(以下))]
当j>b时， 那么dp[i][j] += dp[i-1][(j与b的中点(以下))~n]
由于dp[i][j]的值只跟dp[i-1][]的一些值有关，所以用滚动数组会大大减小内存。
用一个sum[i][j]维护前缀和即可。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #define Mod 1000000007 #define lll __int64 using namespace std; #define N 100007 lll dp[2][5002],sum[2][5002]; int n; int main() { int a,b,k,i,j; while(cin>>n>>a>>b>>k) { memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); dp[0][a] = 1LL; for(i=a;i<=n;i++) sum[0][i] = 1LL; int now = 0; for(i=1;i<=k;i++) { now ^= 1; memset(dp[now],0,sizeof(dp[now])); memset(sum[now],0,sizeof(sum[now])); for(j=1;j<=n;j++) { if(j < b) { int k = (j+b-1)/2; dp[now][j] = (dp[now][j]+sum[now^1][k]-dp[now^1][j])%Mod; } else if(j > b) { int k = (j+b+2)/2; dp[now][j] = (dp[now][j]+sum[now^1][n]-sum[now^1][k-1]-dp[now^1][j])%Mod; } sum[now][j] = (sum[now][j-1]+dp[now][j])%Mod; } } lll sum = 0; for(i=1;i<=n;i++) sum = (sum+dp[now][i])%Mod; cout<<(sum+Mod)%Mod<<endl; } return 0; }