题目链接：http://codeforces.com/contest/479/problem/E
题意：
给定一个启示的楼层a，有一个不能去的楼层b，对于你可以去的下一个楼层必须满足你当前楼层x与下一个要去的楼层y的距离小于x到b的距离。求出走k趟的方案数。
题解：
dp[i][j] 表示第i趟 在第j层楼的方案数。一般用三个for才可以，所以我们用前缀和优化一下，时间复杂度降到O(n*k)。空间复杂度有点大，所以我们可以用滚动数组。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL; 15 typedef pair <int, int> P; 16 const int N = 5005; 17 LL dp[2][N], mod = 1e9 + 7; 18 LL sum[2][N]; 19 20 int main() 21 { 22 int n, a, b, k; 23 cin >> n >> a >> b >> k; 24 dp[0][a] = 1; 25 sum[0][a] = 1; 26 for(int i = 1; i <= k; ++i) { 27 for(int j = 1; j <= n; ++j) { 28 sum[(i - 1)&1][j] += sum[(i - 1)&1][j - 1]; 29 sum[i&1][j] = dp[i&1][j] = 0; 30 } 31 for(int j = 1; j <= n; ++j) { 32 int l, r; 33 if(j > b) { 34 l = (b + j + 1) / 2 + (b + j + 1) % 2, r = n; 35 l = l == j ? l + 1: l, r = r == j ? r - 1: r; 36 if(l > r) 37 continue; 38 } else if(j < b) { 39 l = 1, r = (b + j - 1) / 2; 40 r = r == j ? r - 1: r, l = l == j ? l + 1: l; 41 if(l > r) 42 continue; 43 } else { 44 continue; 45 } 46 //cout << i << " " << j << " = " << l << " " << r << endl; 47 if(l < j && r > j) { // 包含 48 dp[i&1][j] = mod - dp[(i - 1)&1][j]; 49 } 50 dp[i&1][j] += ((sum[(i - 1)&1][r] - sum[(i - 1)&1][l - 1]) % mod + mod) % mod; 51 dp[i&1][j] %= mod; 52 sum[i&1][j] += dp[i&1][j]; 53 sum[i&1][j] %= mod; 54 } 55 } 56 LL ans = 0; 57 for(int i = 1; i <= n; ++i) { 58 ans += dp[k&1][i]; 59 ans %= mod; 60 } 61 cout << ans << endl; 62 return 0; 63 }