DP搬运工之搬运工2
longdie
2020-12-31 14:49:09
**注：以下系列题目为搬运 mengbier（yxy） 的DP经典题目。**
# 题目
给你 $n(n<=50)$， $K(K<=n^2)$，问你有多少个1 到 $n$ 的排列， 满足相邻两个数的 $max$ 的和不超过 $K$, 输出答案 $mod20172019$ 的结果。
# 分析
这应该算是我做过的第一道**预设型DP**。
我们很显然的可以发现，如果从小到大考虑的话，会出现后效性，这就启发我们先预设后面的状态来进行DP和转移。
因为我们一般计算的是**当前情况**的贡献，我们可以通过**限制后面**情况来满足当前。
就本题而言：我们可以通过提前声明数 $x$ 两边可不可以继续填数来进行转移。
显然分三种情况：
1. 两边都不填，那么贡献会增加$2*x$。
2. 填一边，那么会增加$x$的贡献。
3. 都不填，那么不会增加贡献。
当然不要忘了讨论数放在端点上的情况。
我们可以定义 $f[i][j][k]$ 表示填完 $1 - i$, 有 $j$ 个位置可以填数，当前贡献为 $k$时的方案数。
分情况转移即可，复杂度$O(n^2K)$。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read(int x = 0) { return scanf("%d", &x), x; }
const int mod = 20172019, N = 55;
int n, K, f[N][N][N*N], ans = 0;
int main() {
n = read(), K = read();
f[1][0][0] = 1;
for(int i = 2; i <= n; ++i)//采用刷表法进行DP
for(int j = 0; j <= i; ++j)
for(int k = 0; k <= K; ++k) {
int now = (f[i-1][j][k] * 2) % mod;//放在两端的情况。
f[i][j + 1][k] = (f[i][j + 1][k] + now) % mod;
f[i][j][k + i] = (f[i][j][k + i] + now) % mod;
now = f[i-1][j][k] * 1ll * j % mod;//放在中间的情况。
f[i][j + 1][k] = (f[i][j + 1][k] + now) % mod;
f[i][j][k + i] = (f[i][j][k + i] + now * 2ll) % mod;
f[i][j-1][k + 2*i] = (f[i][j-1][k + 2*i] + now) % mod;
}
for(int i = 0; i <= K; ++i) ans = (ans + f[n][0][i]) % mod;//统计答案。
return cout << ans, 0;
}
```