CF479E Riding in a Lift 题解
CF479E Riding in a Lift 题解
题目描述:
假设你现在在一栋有 \(n\) 层的楼里,可以乘坐电梯在各层之间移动。我们将楼层自下而上编号为 \(1\) 到 \(n\)。你目前在第 \(a\) 层。你感到很无聊,于是想乘坐电梯。第 \(b\) 层有一间秘密实验室,不允许进入。不过你已经玩嗨了,决定连续坐 \(k\) 次电梯。
假设你当前在第 \(x\) 层(最初你在第 \(a\) 层)。在每一次电梯旅行中,你选择某一不同于 \(x\) 的楼层 \(y\)(即 \(y \ne x\)),电梯会把你送到那里。因为你不能经过有秘密实验室的 \(b\) 层,所以你决定移动距离 \(|x-y|\) 必须严格小于当前所在楼层到 \(b\) 层的距离 \(|x-b|\)。即,必须满足 \(|x-y| < |x-b|\)。每当你成功移动到 \(y\) 层时,你会把 \(y\) 记到你的笔记本上。
你的任务是,计算经过 \(k\) 次电梯旅行后,你可能在笔记本上记录下的不同数字序列个数。由于最终序列数可能非常大,请将其结果对 \(1000000007\)(\(10^9+7\))取模后输出。
输入格式:
输入的第一行为四个用空格分隔的整数 \(n\)、\(a\)、\(b\)、\(k\),其中 \(2 \leq n \leq 5000\),\(1 \leq k \leq 5000\),\(1 \leq a, b \leq n\),且 \(a \ne b\)。
输出格式:
输出一个整数,表示不同数字序列的总个数,对 \(1000000007\) 取模。
数据范围:
假设你现在在一栋有 \(n\) 层的楼里,可以乘坐电梯在各层之间移动。我们将楼层自下而上编号为 \(1\) 到 \(n\)。你目前在第 \(a\) 层。你感到很无聊,于是想乘坐电梯。第 \(b\) 层有一间秘密实验室,不允许进入。不过你已经玩嗨了,决定连续坐 \(k\) 次电梯。
假设你当前在第 \(x\) 层(最初你在第 \(a\) 层)。在每一次电梯旅行中,你选择某一不同于 \(x\) 的楼层 \(y\)(即 \(y \ne x\)),电梯会把你送到那里。因为你不能经过有秘密实验室的 \(b\) 层,所以你决定移动距离 \(|x-y|\) 必须严格小于当前所在楼层到 \(b\) 层的距离 \(|x-b|\)。即,必须满足 \(|x-y| < |x-b|\)。每当你成功移动到 \(y\) 层时,你会把 \(y\) 记到你的笔记本上。
你的任务是,计算经过 \(k\) 次电梯旅行后,你可能在笔记本上记录下的不同数字序列个数。由于最终序列数可能非常大,请将其结果对 \(1000000007\)(\(10^9+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;
}




