DP搬运工之搬运工3
longdie
2020-12-31 14:49:56
**注：以下系列题目为搬运 直系学长mengbier（yxy） 的DP经典题目。**
# 题目
给定长度为$n$的$1-n$的排列，定义 $magic(A, B) = \sum_{i=1}^{n}max(A_i, B_i)$。现在给定$n, K,$ 问有多少对 $(A, B)$ 满足 $magic(A, B) >= K$。 输出答案 $mod 20172019$ 的结果。
# 分析
首先这题看上去是真的 mengbi, 感觉不知所u云， 但是我们仔细考虑后可以发现，B排列可以固定为$1, 2, 3, ... , n$，然后最后答案只要乘一个 $n!$就可以了。
这题我们首先按照上两题的思路考虑填数，但马上就会发现自己分析都分析不清楚，更不用考虑消除后效性了，那么我们是不是可以尝试固定序列，然后往里面**填数**，
虽然这样还会有后效性，但是我们可以继续用**预设型DP**解决本题的后效性。
那我们如何填数呢？ 可以从小到大填数，然后考虑数的大小 和位置 对答案的影响，分类讨论就可以了。
定义状态 $f[i][j][k]$ 为填了 $1-i$， 有$j$个数填到了$i + 1 - n$ 的位置， 贡献为 $k$ 时的方案数。
考虑各种情况：
1. 将i填到了i的位置，那么 `k += i`。
2. 将i填到了小于i的位置，且位置i填了小于i的数，那么 `k += 2*i`，`--j`。
3. 将i填到了小于i的位置，且位置i填了大于i的数，那么 `k += i`。
4. 将i填到了大于i的位置，且位置i填了小于i的数，那么 `k += i`。
5. 将i填到了大于i的位置，且位置i填了大于i的数，那么 `++j`。
显然的可以合并1，3，4。
### 引用yxy学长的题后感言：
本来写完这篇题解感觉这个题跟预设型 DP 没什么关系，仔细想想它还是用了最关键的部分： **i 产生的贡献就在 i 这轮算**。只不过这个题位置和数都会做贡献，理解起来稍微有点奇怪，但也是个不错的题，起码让我见到了**填数**的 DP 。
## 代码
```
#include <bits/stdc++.h>
using namespace std;
const int N = 55, mod = 20172019;
int n, K, f[N][N][N*N], ans = 0;
int main() {
cin >> n >> K;
f[1][0][1] = f[1][1][0] = 1;//初始化需要仔细想啊。
for(int i = 2; i <= n; ++i)
for(register int j = 0; j <= i; ++j)
for(register int k = 0; k <= K; ++k) {
int now = f[i-1][j][k];
f[i][j + 1][k] = (f[i][j + 1][k] + now) % mod;//方案5
f[i][j][k + i] = (f[i][j][k + i] + now*1ll*(j<<1|1)) % mod;//方案1，3，4
if(j > 0) f[i][j-1][k + 2*i] = (f[i][j-1][k + 2*i] + now*1ll*j*j) % mod;//方案2
}
for(register int i = K; i <= n*n; ++i) //统计答案
ans = (ans + f[n][0][i]) % mod;
for(register int i = 2; i <= n; ++i) //乘n!
ans = ans * 1ll * i % mod;
cout << ans << '\n';
return 0;
}
```