跳转至

线头 dp

泛化ψ(｀∇´)ψ

我也不知道这个称呼最早是在哪里看到的。

我目前能找到的最早的博客是 Itst 的: link

第一个例题是模拟赛遇到过的题目，这也是 zjk 当时讲 dp 专题的一个“难以归类的技巧”，实际上它还是能有泛化的。

让我看懂这个算法的博客是 Sword_K 先生写的：https://www.luogu.com.cn/blog/sword-wjh/loj2743joi-open-2016-ma-tian-tai-lou，在此感谢，第一个例题中的定义和图参考了这篇博客，我只是在这位先生的基础上加上了自己的理解。

例题ψ(｀∇´)ψ

LOJ2743「JOI Open 2016」摩天大楼ψ(｀∇´)ψ

将互不相同的 \(N\) 个整数 \(A_{1}, A_{2}, \cdots, A_{N}\) 按照一定顺序排列。

假设排列为 \(f_{1}, f_{2}, \cdots, f_{N}\)，要求：\(| f_{1} - f_{2}| + | f_{2} - f_{3}| + \cdots + | f_{N-1} - f_{N}| \leq L\)。

求满足题意的排列的方案数对 \(10^9+7\) 取模后的结果。

对于所有数据，\(1\le N\le 100\)，\(1\le L\le 1000\)，\(1\le A_{i}\le 1000\)。

这个题目应该非常适合用来作为线头 dp 的模板题。

其他人的做法大多是使用一种被叫做“连续段dp”的思想，其实本质上来说没有差别。

首先不妨对 \(A\) 排序，我们可以注意到这并不影响我们最后的答案。

我们观察一下这个转移的形式，如果我们把 \(A\) 放到一个数轴上，并记录我们选择的 \(f_{1} \to f_{2} \to \dots\) 的路径。

并且规定，如果方向变换，我们就新开一层，可以发现它长成这个样子：

thread-1

可以发现，按照这样的方式，任意一个排列都能唯一对应一个路径。

所以这就构建了计数问题中最为重要的双射关系，我们现在只需要对长度合法的路径计数就可以了。

考虑在任意一个位置竖向划一刀，我们可以发现，这个横截面（考虑左侧）上存在着多个“线头”，像这样：

thread-2

我们近乎形式化地定义这样的东西为一个“线头”：

thread-3

注意到起点以及终点有可能无法构成一个完整的线头，于是我们做如下规定，将其强制变为一个完整的线头：

（不管是起点还是终点都类似定义）：

thread-4

如果本身能够构成一个完整的线头，我们将起点“封闭”住。

如果本身不能够构成一个完整的线头，我们在上方新加一个虚拟线头，将起点封闭住，终点则是在下方加一个虚拟线头。

在这样的规定之后，我们可以发现，如果我们的横截面扫到了最后一个位置，一条合法路径应当是一个完整的线头，并且起点和终点都封闭住了。

于是我们可以做一个扫描线，然后对线头进行 dp 计数。

设 \(dp(i, j, k, d)\) 表示，当前扫描线在值域上的位置 \(i\)，目前有 \(j\) 个线头，路径长度为 \(k\)，目前有 \(d\) 个端点已经封闭的方案数。

于是我们讨论一下，新加入一个位置 \(A_{f_{i + 1}}\) 对线头形态会有什么影响。

  1. 如果满足 \(A_{f_{i + 1}} > A_{f_{i}}\land A_{f_{i}} < A_{f_{i - 1}}\)，那么此时会增加一个新的线头。
  2. 如果满足 \(A_{f_{i - 1}} < A_{f_{i}}\land A_{f_{i + 1}} < A_{f_{i}}\)，那么此时会合并两个现有的线头。
  3. 另外的情况，就是可以顺着走下去，对线头的形态并没有任何影响。

像这样：

thread-5

另外还有，我们需要考虑封闭端点的边界情况，并在转移的时候考虑能有哪些情况，下面就具体讲一下转移。

首先考虑新增线头的情况，显然此时能够在已有的 \(j\) 个线头形成的 \(j - 1\) 个空和上下两个边界位置任意插入，然后需要注意是不是存在已经被封闭的端点，这个需要去掉。

那么转移就形如 \(dp(i, j, k, d)\times (j + 1 - d) \to dp(i + 1, j + 1, k + (A_{i + 1} - A_{i})(2j - d)), d\)。

路径长度这个也比较好理解，就是考虑每个线头的两端被拉长了这么多，但是要去掉虚拟线头的部分。

然后就是合并线头的情况，和新增比较类似，选择任意两个相邻线头合并起来就行，路线延长还是一样的。

转移形如 \(dp(i, j, k, d) \times (j - 1) \to dp(i + 1, j - 1, k + (A_{i + 1} - A_{i})(2j - d), d)\)。

如果是延长，那么连接处可以放在 \((2j - d)\) 个端点的任意一个后面。

转移形如 \(dp(i, j, k, d) \times (2j - d) \to dp(i + 1, j, k + (A_{i + 1} - A_{i})(2j - d), d)\)。

然后最后考虑将这个位置作为起点或者终点的情况，考虑它向左向右的情况分别转移即可。

不过唯一的区别就是会不会增加虚拟线头。

转移形如 \(dp(i, j, k, d) \times (2 - d) \to dp(i + 1, j\text{ or } j + 1, k + (A_{i + 1} - A_{i})(2j - d), d + 1)\)。

边界显然是 \(dp(0, 0, 0, 0) = 1\)。

答案是 \(\sum\limits_{t \leq L} dp(n, 1, t, 2)\)。

Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// author : black_trees

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
  public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
using modint = static_modint<1000000007>;

template <typename __Tp> void read(__Tp &x) {
    int f = x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
void read(char &ch) { for (ch = getchar(); isspace(ch); ch = getchar()); }
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &... y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
void write(const char *s) { for (; *s; ++s) putchar(*s); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ... y) { write(x), write(y...); }
void read(modint &x) { int __value; read(__value); x = __value; return; } 
void write(modint x) { write(x.val()); }

const int si = 1e2 + 10;
const int siv = 1e3 + 10;

i64 n, l, a[si];
modint dp[si][si][siv][3];

int main() {

#ifndef Enonya
    string fileName = "permutation";
    freopen((fileName + ".in").c_str(), "r", stdin);
    freopen((fileName + ".out").c_str(), "w", stdout);
#endif

    read(n, l);
    if(n == 1) return write(1, endl), 0; 
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);

    dp[0][0][0][0] = 1;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= i; ++j) {
            for(int k = 0; k <= l; ++k) {
                for(int o = 0; o < 3; ++o) {
                    i64 p = k + (a[i + 1] - a[i]) * (j * 2 - o);
                    if(p > l) continue;
                    dp[i + 1][j + 1][p][o] += dp[i][j][k][o] * (j - o + 1);
                    if(j > 1) dp[i + 1][j - 1][p][o] += dp[i][j][k][o] * (j - 1);
                    if(j > 0) dp[i + 1][j][p][o] += dp[i][j][k][o] * (j * 2 - o);
                    if(o < 2) dp[i + 1][j + 1][p][o + 1] += dp[i][j][k][o] * (2 - o);
                    if(o < 2) dp[i + 1][j][p][o + 1] += dp[i][j][k][o] * (2 - o);
                }
            }
        }
    }
    modint cnt = 0;
    for(int i = 0; i <= l; ++i) cnt += dp[n][1][i][2];
    return write(cnt, endl), 0;
}

LOJ2687「BalticOI 2013」Vimψ(｀∇´)ψ

感觉非常简单！我就不写了！

Luogu5999 [CEOI2016] kangarooψ(｀∇´)ψ

感觉有点像是，不过我还没弄。

最后更新: November 15, 2023