Codeforces 479E Riding in a Lift(dp)

本文主要是介绍Codeforces 479E Riding in a Lift(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Codeforces 479E Riding in a Lift

题目大意：有一栋高N层的楼，有个无聊的人在A层，他喜欢玩电梯，每次会做电梯到另外一层。但是这栋楼里有个秘

密实验室在B层，所以每次他移动的时候就有了一个限制，x为当前所在层，y为目标层，|x - y| < |x - b|。问说移动K次

后，有多少不同的路径。

解题思路：dp[i][j]表示在第i步到达j层有多少种不同的路径，dis = abs(j-B) - 1，那么在[j-dis,j+dis]这个范围都能被转

移，除了j。那么转移方程就很好写了。

但是直接转移的话复杂度有点高，因为转移的范围是成段的，所以我们可以利用数组维护区间和的方式取优化。每次对

一个区间l，r加上某个值v的时候，等于在l处+v，r+1处-v，最后处理的时候每个位置的准确值即为数组的前缀和。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>using namespace std;const int maxn = 5005;
const int mod = 1e9 + 7;int N, A, B, K, dp[maxn][maxn];void add (int idx, int l, int r, int d) {dp[idx][l] = (dp[idx][l] + d) % mod;dp[idx][r] = (dp[idx][r] - d + mod) % mod;
}int main () {scanf("%d%d%d%d", &N, &A, &B, &K);dp[0][A] = 1;for (int i = 0; i < K; i++) {for (int j = 1; j <= N; j++) {if (j == B) continue;int x = abs(j - B) - 1;add(i+1, max(j-x, 1), j, dp[i][j]);add(i+1, j+1, min(j+x+1, N + 1), dp[i][j]);}int mv = 0;for (int j = 1; j <= N; j++) {mv = (mv + dp[i+1][j]) % mod;dp[i+1][j] = mv;}}int ans = 0;for (int i = 1; i <= N; i++)ans = (ans + dp[K][i]) % mod;printf("%d\n", ans);return 0;
}

这篇关于Codeforces 479E Riding in a Lift(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---