Codeforces 479E. Riding in a Lift (dp + 前缀和优化)

题目链接：http://codeforces.com/contest/479/problem/E

题意：

        给定一个启示的楼层a，有一个不能去的楼层b，对于你可以去的下一个楼层必须满足你当前楼层x与下一个要去的楼层y的距离小于x到b的距离。求出走k趟的方案数。

题解：

　　dp[i][j]  表示第i趟 在第j层楼的方案数。一般用三个for才可以，所以我们用前缀和优化一下，时间复杂度降到O(n*k)。空间复杂度有点大，所以我们可以用滚动数组。

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = ;

 LL dp[][N], mod = 1e9 + ;

 LL sum[][N];

 int main()

 {

     int n, a, b, k;

     cin >> n >> a >> b >> k;

     dp[][a] = ;

     sum[][a] = ;

     for(int i = ; i <= k; ++i) {

         for(int j = ; j <= n; ++j) {

             sum[(i - )&][j] += sum[(i - )&][j - ];

             sum[i&][j] = dp[i&][j] = ;

         }

         for(int j = ; j <= n; ++j) {

             int l, r;

             if(j > b) {

                 l = (b + j + ) /  + (b + j + ) % , r = n;

                 l = l == j ? l + : l, r = r == j ? r - : r;

                 if(l > r)

                     continue;

             } else if(j < b) {

                 l = , r = (b + j - ) / ;

                 r = r == j ? r - : r, l = l == j ? l + : l;

                 if(l > r)

                     continue;

             } else {

                 continue;

             }

             //cout << i << " " << j << " = " << l << " " << r << endl;

             if(l < j &&  r > j) { // 包含

                 dp[i&][j] = mod - dp[(i - )&][j];

             }

             dp[i&][j] += ((sum[(i - )&][r] - sum[(i - )&][l - ]) % mod + mod) % mod;

             dp[i&][j] %= mod;

             sum[i&][j] += dp[i&][j];

             sum[i&][j] %= mod;

         }

     }

     LL ans = ;

     for(int i = ; i <= n; ++i) {

         ans += dp[k&][i];

         ans %= mod;

     }

     cout << ans << endl;

     return ;

 }