DP搬运工之搬运工1

longdie · 2020-12-31 14:48:22 · 个人记录

注：以下系列题目为搬运 mengbier（yxy） 的DP经典题目。

题目

给你 n(n<=3000), K(K<=3000), 求有多少个1到n 的排列， 恰有 K 个数 i(1<i<n) 满足 a_{i-1}, a_{i+1} 都小于 a_i，输出答案 mod 20172019 即可。

分析

本题其实是最简单的一道。 我们考虑从小到大加入数 i，那么只要 i 放在任意两个数中间都会增加一个新的贡献。 那么我们可以定义 f[i][j] 为考虑完 1 - i, 有 j 对满足要求的方案数。 考虑转移，我们可以以j是否增加来转移。 这样分两种情况即可。

1. j不增加 那么如果i放在任意一个满足条件的数中间，都会减少一对, 并且会增加一对， 所以不增不减。 还有如果i放在两边，也会不增加。
2. j增加 除了不增加的地方，别的地方都增加。

时间复杂度O(nK)。 详解看代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 20172019, N = 3005;
int n, k, f[N][N];
int main() {
    cin >> n >> k;
    f[1][0] = 1, f[2][0] = 2;//初始化
    for(int i = 3; i <= n; ++i) 
        for(int j = 0; j <= min(k, i); ++j) 
            f[i][j] = (f[i][j] + f[i-1][j] * 1ll * ((j + 1) << 1)) % mod, //j不增加
            f[i][j + 1] = (f[i][j + 1] + f[i-1][j] * 1ll * (i-2 - (j << 1))) % mod;//j增加
    cout << f[n][k] << '\n';
    return 0;
}