[HG]小G坐电梯 题解

C 小G坐电梯

题目描述

小G来到了著名的某大厦。大厦一共有n层，初始的时候小G在第 A 层。

小G特别想去B层小 M 的办公室看一看，然而因为安保原因，B层已经被封锁无法进入。

但是小G既然来了，就想在大厦里面逛一逛。大厦里面有一部电梯，小G决定坐 k 次电梯。

因为小G比较无聊，他给自己设定了这样一个规矩：假如当前他在x层，则他要去的下一个楼层y和x的楼层差必须要小于 x 和 B 的楼层差，即 \(|x−y| < |x−B|\) 。

每到达一个楼层，小G都要记录下来其楼层号。

当小G转完一圈后，他也记录下了 \(k + 1\) 个楼层号（可能有重复）。

小G现在 想知道，按照他定下的规矩，一共有多少种可能的楼层号序列？

题解

定义f[i][j][k]为当前走了i步，距离终点为j的，方向为k(0向下，1向上)。

暴力DP+前缀和，滚动数组压掉一维。

代码

#include <cstdio>

#include <cmath>

using namespace std;

#define max(a,b) ((a>b)?a:b)

const int MOD = 1e9 + 7;

           //k     dlt  lft 0:dwn, 1:up

long long f[10005][2];

long long pre[20005][2];

int mx_dlt, dlt;

inline long long pls(long long a, long long b){

    return ((a + b >= MOD) ? (a + b - MOD) : (a + b));

}

inline void getPre(){

    pre[0][0] = pre[0][1] = 0;

    for (int j = 1; j <= mx_dlt; ++j){

        pre[j][0] = pls(pre[j - 1][0], f[j][0]);

        pre[j][1] = pls(pre[j - 1][1], f[j][1]);

    }

    for (int j = mx_dlt + 1; j <= mx_dlt * 2; ++j){

        pre[j][0] = pre[j - 1][0];

        pre[j][1] = pre[j - 1][1];

    }

}

int main(){

    freopen("lift.in", "r", stdin);

    freopen("lift.out", "w", stdout);

    int n, A, B, k; scanf("%d %d %d %d", &n, &A, &B, &k);

    mx_dlt = max(B * 2, abs(n - B) * 2); dlt = abs(A - B);

    f[dlt][0] = (A < B), f[dlt][1] = (A > B);

    getPre();

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

        for (int j = 1; j <= mx_dlt; ++j){

            int tmp0 = f[j][0], tmp1 = f[j][1];

            if (B - j > 0)

                f[j][0] = ((pre[mx_dlt][0] - pre[j / 2][0] - tmp0) % MOD + MOD) % MOD;

            if (B + j <= n)

                f[j][1] = ((pre[mx_dlt][1] - pre[j / 2][1] - tmp1) % MOD + MOD) % MOD;

        }

        getPre();

    }

    long long ans = (pre[mx_dlt][0] + pre[mx_dlt][1] + MOD * 2) % MOD;

    printf("%lld", ans);

    return 0;

}