CF479E Riding in a Lift 题解

题目链接：CF479E Riding in a Lift

题意：

现在有n个传送点呈序列排列，编号为1到n
每一次可以通过折跃从一个传送点传送到另一处传送点，
由于折跃需要消耗巨大的能量，因此每次传送的距离小于出发传送点到能量水晶的距离，能量水晶在编号为b的传送点上，
即对于编号为x的出发点，目标传送点的编号y要满足如下的要求：
|x-y|<|x-b| (x≠y)
同时，由于能量水晶储存着巨大的能量，严禁随意接近，因此你不能传送到b号传送点。

无聊的你想知道，在a号传送点的你，经过k次折跃之后，能有多少种不同的传送点访问序列

输入一行四个数：
n,a,b,k，
其中 2≤n≤5000,1≤k≤5000,1≤a,b≤n,且保证a≠b

输出一行为总的序列数，答案要对1000000007取模（1e9+7）

dp大水题，模拟赛花了十几分钟就A了

用刷表法更新答案

每个点 $j$ （除了 $b$ ，它不更新）能更新的范围都是

$$\left[\max(1,j-|j-b|+1),j) \cup (j,\min(n,j+|j-b|-1)\right]$$

直接暴力去更新肯定是不行的

注意到其实它的更新是区间加，考虑差分，然后去掉「跳到自己」的贡献

时间复杂度 $O(nk)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e3+15)

const int p=1e9+7;
int n,a,b,k,f[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> a >> b >> k;
    f[0][a]=1;
    for(int i=0; i<k; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(j==b)continue;
            int t=abs(j-b);
            int l=max(1ll,j-t+1),r=min(n,j+t-1);
            f[i+1][l]=(f[i+1][l]+f[i][j])%p;
            f[i+1][r+1]=((f[i+1][r+1]-f[i][j])%p+p)%p;
            // for(int k=l; k<=r; k++)
            //     if(k!=b&&k!=j)f[i+1][k]=(f[i+1][k]+f[i][j])%p;
        }
        for(int j=1; j<=n; j++)
                f[i+1][j]=(f[i+1][j-1]+f[i+1][j])%p;
            for(int j=1; j<=n; j++)
                f[i+1][j]=((f[i+1][j]-f[i][j])%p+p)%p;
    }
    int res=0;
    for(int i=1; i<=n; i++)
        res=((res+f[k][i])%p+p)%p;
    cout << res << '\n';
    return 0;
}