题意很简单吧。
从a点出发，走k步，每步的限制是，假设现在在x，要到y去，那么必须|x-y|<|x-b| 注意不能到b上，而且每步不能原地踏步
问经过这k步，能形成多少不同的路径
然后这题就比较裸
令dp[k][i] 表示走到第k步，最后一步到i的路径数
那么有状态转移
dp[k+1][j] += dp[k][i] 其中j是满足 |i - j| < |i - b|的所有的数
发现是n^3的 ，n是5000
那么这种现象就有个技巧
假设dp[j] (l<=j<=r) 都要加上一个数x
那么新开一个数组s
s[l] += x
s[r + 1] -= x
最后
sum(s[1],s[2],...,s[i]) 表示的就是dp[i]的变化
那么就优化成n^2的了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <map>
#define MAXN 111
#define MAXM 55555
#define INF 1000000007
using namespace std;
int dp[5555], sum[5555];
int n, a, b, k;
int main()
{scanf("%d%d%d%d", &n, &a, &b, &k);dp[a] = 1;for(int i = 1; i <= k; i++) {for(int j = 0; j <= n; j++) sum[j] = 0;for(int j = 1; j <= n; j++) {int t = abs(j - b) - 1;int l = max(1, j - t);int r = min(j + t, n);sum[l] += dp[j];if(sum[l] >= INF) sum[l] -= INF;sum[r + 1] -= dp[j];if(sum[r + 1] < 0) sum[r + 1] += INF;}int s = 0;for(int j = 1; j <= n; j++) {s += sum[j];if(s >= INF) s -= INF;dp[j] = s - dp[j];if(dp[j] < 0) dp[j] += INF;}}int ans = 0;for(int j = 1; j <= n; j++) {ans += dp[j];if(ans >= INF) ans -= INF;}printf("%d\n", ans);return 0;
}