DP搬运工之搬运工3

· · 个人记录

注：以下系列题目为搬运 直系学长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;
}