题意很简单吧。
从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; }