[COGS] 电梯

题目描述题目描述输入格式输出格式样例输入样例输出提示 解题过程搜索&DP差分优化差分实现代码 感想

题目描述

题目描述

无所事事的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