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)。

代码

#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;
}