传送门
文章目录- 题意
- 思路
- 代码
给定 N , M , K {N,M,K} N,M,K ，数组 a 1 , a 2 , . . . , a N {a_1,a_2,...,a_N} a1,a2,...,aN，满足如下两个条件
1 < = A i < = M ， ( 1 < = i < = N ) ∣ A i − A i + 1 ∣ > = K ， ( 1 < = i < = N − 1 ) begin{aligned} & 1<=A_i<=M， && (1<=i<=N) \ & |A_i-A_{i+1}| >=K，&& (1<=i<=N-1) end{aligned} 1<=Ai<=M，∣Ai−Ai+1∣>=K，(1<=i<=N)(1<=i<=N−1)
求构成这样的序列的总方案数。
思路
定 义 ： d p [ i ] [ j ] ： 表 示 确 定 A 的 前 i 项 的 方 法 数 ， 使 得 第 i 项 为 j 转 移 方 程 ： d p [ i + 1 ] [ j ] = ( d p [ i ] [ 1 ] + . . . + d p [ i ] [ j − k ] ) + ( d p [ i ] [ j + k ] + . . . + d p [ i ] [ M ] ) begin{aligned} 定义：\\ & dp[i][j]：表示确定A的前i项的方法数，使得第i项为j \ \ 转移方程：\\ & dp[i + 1][j] = (dp[i][1] + ...+dp[i][j-k]) + (dp[i][j + k] + ...+dp[i][M]) end{aligned} 定义：转移方程：dp[i][j]：表示确定A的前i项的方法数，使得第i项为jdp[i+1][j]=(dp[i][1]+...+dp[i][j−k])+(dp[i][j+k]+...+dp[i][M])
显然如上转移，时间复杂度为 O ( N M 2 ) {O(NM^2)} O(NM2)，不可接受。
那么我们可以在计算 d p [ i + 1 ] {dp[i + 1]} dp[i+1] 时，先处理好 d p [ i ] {dp[i]} dp[i] 的状态，然后进行 O ( 1 ) {O(1)} O(1) 得到。
那么时间复杂度很好的优化到了 O ( N M ) {O(NM)} O(NM)。
解法中会用到：
-
二维压一维
- 计算当前 i + 1 {i+1} i+1 的状态，只与 i {i} i 层状态有关。
-
前缀和优化
- 前缀和数组 s {s} s
- d p [ i ] = s [ m ] − s [ j + k − 1 ] + s [ j − k + 1 ] {dp[i] = s[m] - s[j + k - 1] + s[j-k+1]} dp[i]=s[m]−s[j+k−1]+s[j−k+1]
还需注意的是当 k = = 0 {k == 0} k==0 时：
- 无需后两项， d p [ i ] = s [ m ] {dp[i] = s[m]} dp[i]=s[m]
代码
- 前缀和 + 动态规划
int n, m, k;
int f[M], s[M];
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) f[i] = 1; // i == 1;
for (int i = 2; i <= n; i++) { // i > 1
s[0] = 0;
for (int j = 1; j <= m; j++)
s[j] = (s[j - 1] + f[j]) % mod;
int sum = s[m];
for (int j = 1; j <= m; j++) {
int l = max(1ll, j - k + 1);
int r = min(m, j + k - 1);
if(k > 0) f[j] = (sum - s[r] + s[l - 1] + mod) % mod;
else f[j] = sum % mod;
}
}
int res = 0;
for (int i = 1; i <= m; i++) res = (res + f[i]) % mod;
cout << res << endl;
}
