帝国大厦

题目描述

帝国大厦共有 $n$ 层，LZH 初始时在第 $a$ 层上。
帝国大厦有一个秘密实验室，在第 $b$ 层，这个实验室非常特别，对 LZH 具有约束作用，即若 LZH 当前处于 $x$ 层，当他下一步想到达 $y$ 层时，必须满足 $|x-y|<|x-b|$，而且由于实验室是不对外开放的，电梯无法停留在第 $b$ 层。
LZH 想做一次旅行，即他想按 $k$ 次电梯，他想知道不同的旅行方案个数有多少个。
两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。

输入格式

一行 $4$ 个数 $n,a,b,k$。

输出格式

一个数表示答案，由于答案较大，将答案对 $10^9+7$ 取模后输出。

数据范围与子任务

对于 $40\%$ 的数据 $n,k\le 500$。
对于 $80\%$ 的数据 $n,k\le 2000$。
对于 $100\%$ 的数据 $n,k\le 5000, 1 \le a,b \le n, a\neq b$。

测试用例

1

输入

5 2 4 1

输出

2

2

输入

5 2 4 2

输出

2

3

输入

5 3 4 1

输出

0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 5005
const ll mod = 1000000007;
ll n, a, b, k, ans = 0;
ll pre[MAXN],     //上一次按完按钮后到达各楼层的方案数的前缀和
    dp[2][MAXN];  //dp[i&1][j]表示按键i次后到达楼层j的方案数,但是由于内存限制,只能开小一点的数组(用&1来交替使用这两维)

int main() {
    cin >> n >> a >> b >> k;
    dp[0][a] = 1;                  //一开始站的位置只有一种方案
    for (ll i = a; i <= n; ++i) {  //初始化前缀和
        pre[i] = 1;
    }
    for (ll i = 1; i <= k; i++) {      //按了k次按钮
        for (ll x = 1; x <= n; ++x) {  //遍历楼层，x表示现在的楼层
            if (x > b) {               //如果楼层数大于b，就不可能由(b+x)/2前面的楼层到达这里
            //从(b+x)/2往后的楼层才能到达当前楼层x
            //通过之前保存的前缀和更新当前到达楼层x的方案数(注意要减去上一次到达x的方案数,因为pre储存时也包含了到达x的方案数)
            //加mod是为了防止取余后前缀和相减得负
                dp[i & 1][x] = (pre[n] % mod - pre[(x + b) / 2] % mod - dp[(i - 1) & 1][x] % mod + mod) % mod;
            } else if (x < b) {  //如果楼层数小于b，就不可能由(x+b-1)/2后面的得到现在的状态
            //从(x+b-1)/2往前的楼层才能到达当前楼层x
                dp[i & 1][x] = (pre[(x + b - 1) / 2] % mod - pre[0] % mod - dp[(i - 1) & 1][x] % mod + mod) % mod;
            }
        }
        for (ll j = 1; j <= n; ++j) {  //更新前缀和
            pre[j] = (dp[i & 1][j] % mod + pre[j - 1] % mod) % mod;
        }
    }
    for (ll i = 1; i <= n; ++i) {  //统计按键k次后的总方案数
        ans = (ans % mod + dp[k & 1][i] % mod) % mod;
    }
    cout << ans;
    return 0;
}