简单的动态规划题。
绝对详细！
题意
给定三个整数 \(n\)、\(m\) 和 \(k\)，求有多少个序列满足以下条件：
- 对于 \(1 \leqslant i \leqslant n\)，\(1 \leqslant a_i \leqslant m\)。
- 对于 \(1 < i \leqslant n\)，\(\left\vert a_i - a_{i - 1} \right\vert \geqslant k\)。
答案对 \(998244353\) 取模。
思路
求方案数？首先考虑用动态规划。
- 状态：\(dp_{i,j}\) 表示考虑前 \(i\) 个数，且第 \(i\) 个数为 \(j\) 的方案数。
- 转移：
- 如果 \(k \neq 0\)，则 \(dp_{i,j} = (\sum\limits_{1 \leqslant l \leqslant j - k} dp_{i - 1,l} + \sum\limits_{j + k \leqslant l \leqslant m} dp_{i - 1,l})\)。
- 如果 \(k = 0\)，则 \(dp_{i,j} = \sum\limits_{1 \leqslant l \leqslant m} dp_{i-1,l}\)。
- 初始状态：对于 \(1 \leqslant i \leqslant m\)，\(dp_{1,i}=1\)。
- 目标状态：\(\sum\limits_{1 \leqslant i \leqslant m} dp_{n,i}\)。
我们可以敲出一个暴力，时间复杂度：\(O(n ^ 2 \times m)\)，点这里，可以发现只能过一半的测试点。
这时，我们发现：转移是一段区间的和！考虑前、后缀和优化，将转移优化至 \(O(1)\)。
由于有了前后缀和，我们就可以省略掉 \(i\) 这个维度，记得取模。
时空复杂度
- 时间复杂度：\(O(n \times m)\)。
- 空间复杂度：\(O(m)\)。
代码
点击查看代码
#include <iostream>
using namespace std;
using ll = long long;
const int mod = 998244353;
ll dp[5010], sum[5010], num[5010]; // 我为了防止爆 int，开了 long long
int n, m, k;
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) { // 初始状态
sum[i] = sum[i - 1] + 1;
}
for (int i = m; i; i--) {
num[i] = num[i + 1] + 1;
}
for (int i = 2; i <= n; i++) { // 枚举处理前几个，第 1 个已经处理了
for (int j = 1; j <= m; j++) { // 枚举当前位置上的数值
if (k == 0) { // 分类讨论，因为当 k = 0 时上一位数值为 j 的方案数会算两次
dp[j] = sum[m];
} else {
dp[j] = 0;
if (j > k) { // 确保下标不越界
dp[j] = sum[j - k]; // 前缀
}
if (j + k <= m) {
dp[j] = (dp[j] + num[j + k]) % mod; // 后缀
}
}
}
for (int j = 1; j <= m; j++) { // 更新前缀和
sum[j] = (sum[j - 1] + dp[j]) % mod;
}
for (int j = m; j; j--) { // 更新后缀和
num[j] = (num[j + 1] + dp[j]) % mod;
}
}
cout << sum[m]; // 偷懒，sum[m] = dp[1] + dp[2] + ... + dp[m]，不用再算一遍，同理 num[1] 也可以
return 0;
}