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