[COGS] 电梯

题目描述

题目描述

无所事事的Cinzo决定用坐电梯的方式来打发时间。他住在一个N层的房子中，最底下为1层，最高处为N层。他从他家所在的第A层出发，并决定连续坐K次电梯。

但由于迷信的缘故，B在中国被视为是不幸运的，所以整座楼并没有第B层。也是因为这个原因，如果Cinzo想从第X层出发到达第Y层，他希望Y能满足|X - Y| < |X - B|。

每次电梯到达后，Cinzo都会将电梯所到的层数记录在小本子上；K次电梯都坐完后，他将得到一个长度为K的数列。现在，Cinzo想知道，他可能写出多少个不同的数列？

输入格式

一行四个整数，N,A,B,K，分别代表电梯的层数，Cinzo最初的位置，不幸运的层数，以及乘坐电梯的次数。

输出格式

一个整数，代表不同的数列数。（结果对1000,000,007取模）

样例输入

5 2 4 2

样例输出

2

提示

对于20%的数据，N<=10, K<=5；
对于60%的数据，N,K<=100；
对于100%的数据，N,K<=5000。

解题过程

搜索&DP

设 $dp[i][j]$ 为 第 $i$ 次乘坐电梯到 $j$ 层的方案数

很容易推出动态转移方程

$dp[0][a]=1$
$dp[i+1][k]=dp[i+1][k]+dp[i][j],k=j?|j?b|+1,j?|j?b|+2,\dots ,j?1,j+1,\dots ,j+|j?b|?2,j+|j?b|?1$

很暴力

分数：50

差分优化

这时我们通过观察发现 循环加上去的都是同一个数，一次加一整大片，但是循环这么耗时，我们可以通过差分来进行优化

差分

差分 顾名思义，就是第二个数减去前一个数的差组成的数组

差分数组的前缀和等于原数组

我们可以通过修改两端的数来直接修改整个区间

实现

设 $h[i][j]$ 为 $dp[i][j]$ 的差分数组

$dp[0][a]=1$
$h[i+1][j?|j?b|+1]=h[i+1][j?|j?b|+1]+dp[i][j]$
$h[i+1][j+|j?b|]=h[i+1][j+|j?b|]?dp[i][j]$
于是
$dp[i+1][j]={\sum }_{k=1}^{j}h[i+1][k]$ 用 $O(n)$ 的循环累加即可

这里我直接用一个 $dp$ 数组完成 差分 和 动归 两个作用

分数：100

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 * 5 + 10;
const int mod = 1e9 + 7;
int n ,a ,b ,k;
ll dp[MAXN][MAXN] = {
    0};
int abs (int x) {
    if (x < 0) return - x;return x;
}
int main () {
    freopen ("dianti.in","r",stdin);freopen ("dianti.out","w",stdout);scanf ("%d%d%d%d",&n ,&a ,&b ,&k);dp[0][a] = 1;for (int q = 0;q < k;++ q) {
    for (int w = 1;w <= n;++ w) {
    if (w == b) continue ;if (dp[q][w]) {
    int dis = abs (b - w) - 1;dp[q + 1][max (1 ,w - dis)] = (dp[q + 1][max (1 ,w - dis)] + dp[q][w]);dp[q + 1][w] = (dp[q + 1][w] - dp[q][w]);dp[q + 1][w + 1] = (dp[q + 1][w + 1] + dp[q][w]);dp[q + 1][min (n + 1 ,w + dis + 1)] = (dp[q + 1][min (n + 1 ,w + dis + 1)] - dp[q][w]);}}ll x = 0;for (int w = 1;w <= n;++ w) {
    x = (x + dp[q + 1][w]);dp[q + 1][w] = x % mod;}}ll ans = 0;for (int q = 1;q <= n;++ q) {
    if (q == b) continue ;ans = (ans + dp[k][q]) % mod;}
// for (int q = 0;q <= k;++ q) {//调试
// for (int w = 1;w <= n;++ w) {
    
// printf ("%d ",dp[q][w]);
// }
// printf ("\n");
// }printf ("%lld\n",ans % mod);return 0;
}

感想

谢谢大家

——2020.10.4