连通块DP

本篇讨论排列构造中的连通块DP,也称插入DP:按数值顺序处理元素,记录它们在最终排列中形成的片段,再通过新建、延长、合并片段完成构造。

连续段DP 在顺序固定的序列上维护结尾状态;本篇需要构造排列,处理顺序与最终位置顺序不同。阅读前需掌握基础DP、全排列 和 排列与组合。

1 按值插入

给定 nn 个互不相同的数,要构造它们的排列。若按最终位置从左到右选数,就要记住哪些数已经使用,状态可能包含整个集合。

另一种顺序是先排序,按 a1<a2<⋯<ana_1<a_2<\cdots<a_n 依次处理。此时已处理的集合固定为前 ii 个数,不必再保存一个任意子集。

但这些数在最终排列中未必相邻。例如,最终排列为:

最终排列:2 5 1 4 3
处理到3:[2] ? [1] ? [3]
处理到4:[2] ? [1 4 3]
处理到5:[2 5 1 4 3]

? 表示将来由更大元素填充的非空间隔。已处理元素之间已经确定的相邻关系,组成一个连通块。

1.1 块的含义

块是最终排列中由已处理元素组成的极大连续片段。同一块内部的相邻关系已经固定,后续不能再插入元素将它拆开;不同块之间至少还要放一个未处理元素。

本篇保留块的左右顺序,块内部也有方向。因此 [1 3] | [2] 与 [2] | [1 3] 是不同状态。竖线表示尚待填充的间隔,不是已经相邻。

若当前有 jj 个块,加入下一个元素 xx 时,根据它在最终排列中的左右邻居是否已处理,有三类操作:

操作 结构示意 块数变化
新建 `[A] [x]
延长 `[A x] [B]或[A]
合并 [A x B] j−1j-1

其中 A,BA,B 表示整块;合并时只连接当前顺序中相邻的两块。

2 基础计数

先不加任何费用和位置限制,用所有排列检验状态与系数。

2.1 状态定义

令 Fi[j]F_i[j] 表示前 ii 个元素组成 jj 个有序非空块的方案数。它保存内部排列和块间顺序,但没有指定未来间隔的长度。

初始化 F0[0]=1F_0[0]=1。空配置加入第一个元素,只能新建一块。

2.2 转移系数

从一个有 jj 块的配置出发:

  • 新建块:可放在最左、最右或相邻块之间,共 j+1j+1 个位置。
  • 延长块:每块左右各有一个边界,共 2j2j 种选择。
  • 合并块:相邻块之间有 j−1j-1 个间隔,选择一个放入新元素,共 j−1j-1 种。

因此:

Fi+1[j+1]+=Fi[j](j+1),Fi+1[j]+=Fi[j]⋅2j,Fi+1[j−1]+=Fi[j](j−1)(j≥2). \begin{aligned} F_{i+1}[j+1]&\mathrel{+}=F_i[j](j+1),\\ F_{i+1}[j]&\mathrel{+}=F_i[j]\cdot2j,\\ F_{i+1}[j-1]&\mathrel{+}=F_i[j](j-1)\qquad(j\ge2). \end{aligned}

不能把最后一个系数换成任意两块的选择数:本状态已固定左右顺序,只有相邻两块能被新元素直接连接。若采用无序路径集合等其他状态定义,系数需要重新推导。

2.3 不重不漏

删除新加入的最大元素,根据它在块中有零个、一个或两个邻居,分别还原为新建、延长或合并前的唯一配置。因此三类转移不重不漏。

块数足以决定上述操作的数量,块内具体数值不会改变系数,故可以把不同配置按块数汇总。

2.4 手算示例

已处理元素数 ii Fi[1]F_i[1] Fi[2]F_i[2] Fi[3]F_i[3] Fi[4]F_i[4]
1 1 0 0 0
2 2 2 0 0
3 6 12 6 0
4 24 72 72 24

全部元素处理完后,只接受一个块,得到 Fn[1]=n!F_n[1]=n!。多个块之间仍需填数,此时已经没有剩余元素,不能作为最终答案。

还可用 Fi[j]=i!(i−1j−1)F_i[j]=i!\binom{i-1}{j-1} 核对:先排列 ii 个元素,再从 i−1i-1 个内部间隙中选 j−1j-1 个切开。暂时无法完成的多块配置可以保留,它们不会进入最终答案。

3 端点限制

最终排列有左、右两个端点。若某个已处理元素被指定占据最终端点,就不能再向它外侧接数,也不能在它外侧新建块。

维护 b∈{0,1,2}b\in\{0,1,2\},表示两个最终端点中已有几个被占据。这里计数的是端点位置;n=1n=1 时,同一个元素占据两个端点。

3.1 开放边界

jj 个块有 2j2j 个边界,其中 bb 个已经是最终端点,不再连接其他元素。因此开放边界数为:

q=2j−b. q=2j-b.

只保存块数不够:一个块两端都开放时,后续可继续延长;两端都占据最终端点时,整条排列已经封闭,不能再放剩余元素。

3.2 端点转移

新元素可以不占最终端点,也可以占一个尚未确定的最终端点。已存在其他元素时,它不可能同时占据两端。

操作 新块数 新端点数 系数
新建普通块 j+1j+1 bb j+1−bj+1-b
延长普通边界 jj bb 2j−b2j-b
合并相邻两块 j−1j-1 bb j−1j-1
新建块,并占一个最终端点 j+1j+1 b+1b+1 2−b2-b
延长最外侧块,并占一个最终端点 jj b+1b+1 2−b2-b

前两项排除已封闭的边界或外侧位置。后两项只能发生在尚未占据的左端、右端,各提供一种选择;仅在 b<2b<2 时可用。

例如左端未占据时,既可在所有块左侧新建 [x] 并指定它为最终左端,也可将 xx 接在最左块左边并指定为最终左端。这是两种不同操作。

按 bb 汇总是安全的,因为左右两侧在当前模型中对称。若规则区分左、右端,例如首尾元素预先固定,就需要分别记录或按特定元素分类,不能直接沿用这张表。

当 j=1,b=2j=1,b=2 时,所有可用系数均为 0,无法继续插入。只有已处理全部元素时,这才是合法终态,因而不会提前封闭后再接入其他块。

4 摩天大楼

题目:luogu P9197: P9197:[JOI Open 2016] 摩天大楼。

将 nn 个不同高度排成一行,要求相邻高度差的绝对值之和不超过 LL,统计排列数,对 109+710^9+7 取模:

∑t=1n−1∣ft+1−ft∣≤L. \sum_{t=1}^{n-1}|f_{t+1}-f_t|\le L.

原题范围为 n≤100n\le100、L≤1000L\le1000、1≤ai≤10001\le a_i\le1000。排序后依次插入高度,但最终排列可以是任意顺序。

4.1 高度差贡献

设已经处理到 aia_i,下一高度为 ai+1a_{i+1},高度差为 Δ=ai+1−ai\Delta=a_{i+1}-a_i。

在最终排列中,每条连接低处与高处的相邻边,都会在这个高度差上贡献 Δ\Delta。当前块内的边两端均已处理,不再跨越这段高度差;每个开放边界则恰好对应一条连向更高元素的边。

因此,跨过本次高度差时,费用增加:

Δc=(2j−b)(ai+1−ai). \Delta c=(2j-b)(a_{i+1}-a_i).

例如排序高度为 2,5,92,5,9,最终排列为 [5, 2, 9]。处理完高度 5 后有一个块 [5, 2],左端已占据,故 j=1,b=1j=1,b=1。在高度差 9−5=49-5=4 上,只有右侧边界仍开放,增加费用 4。

更早的高度差 5−2=35-2=3 被两条边跨越,贡献 2×3=62\times3=6。总费用为 6+4=106+4=10,恰好等于 ∣5−2∣+∣2−9∣|5-2|+|2-9|。

这是将边长按高度差拆开累计。每条边被它跨越的各段高度差各计一次,总和仍是原边长。费用状态不必保存每条开放边的另一端是谁。

4.2 状态与转移

定义 Di[j][b][c]D_i[j][b][c]:已放入前 ii 个高度,形成 jj 个有序块,占据 bb 个最终端点,按高度差累计到 aia_i 的费用恰为 cc 的方案数。

cc 不只是已确定块内边的费用;它还包含开放边已经跨过的高度差贡献。

从第 ii 层转移到第 i+1i+1 层时:

  1. 用插入前的 j,bj,b 计算 c′=c+(2j−b)(ai+1−ai)c'=c+(2j-b)(a_{i+1}-a_i)。
  2. 若 c′>Lc'>L,舍弃;后续费用非负,不会降回限制内。
  3. 按端点转移表的五种操作,更新对应的 j′,b′j',b':
Di+1[j′][b′][c′]+=Di[j][b][c]⋅对应系数. D_{i+1}[j'][b'][c']\mathrel{+}=D_i[j][b][c]\cdot\text{对应系数}.

所有计数均对 109+710^9+7 取模。转移只依赖 i,j,b,ci,j,b,c,不同历史的具体排列不会改变费用增量和合法操作数量,因此可以合并计数。

4.3 初值与答案

放入最小元素时,还没有跨过高度差,费用为 0:

D1[1][0][0]=1,D1[1][1][0]=2,D1[1][2][0]=1. D_1[1][0][0]=1,\qquad D_1[1][1][0]=2,\qquad D_1[1][2][0]=1.

它可以不占端点、仅占左端或右端、同时占据两端。最后一种情况仅在 n=1n=1 时能完成,其余情况会因无法继续插入而自然消失。

最终必须只有一个块,且两个最终端点均已确定:

ans=∑c=0LDn[1][2][c]. ans=\sum_{c=0}^{L}D_n[1][2][c].

每个完整排列的端点标记唯一;从它删去较大元素,还能唯一恢复各层的块。因此,这些标记不会重复统计最终排列。

4.4 代码实现

下面使用两层数组,保留块数、端点数与费用:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;
using Layer = vector<vector<vector<int>>>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, limit;
    if (!(cin >> n >> limit)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin() + 1, a.end());

    // dp[块数][已占最终端点数][累计费用]
    Layer dp(n + 1, vector<vector<int>>(3, vector<int>(limit + 1)));
    dp[1][0][0] = 1;
    dp[1][1][0] = 2; // 占左端或右端。
    dp[1][2][0] = 1; // 只有 n=1 时能以此状态完成。

    for (int i = 1; i < n; i++) {
        int gap = a[i + 1] - a[i];
        Layer next(n + 1, vector<vector<int>>(3, vector<int>(limit + 1)));

        for (int j = 1; j <= i; j++) {
            for (int b = 0; b <= 2; b++) {
                int extra = (2 * j - b) * gap;
                if (extra > limit) continue;

                for (int cost = 0; cost + extra <= limit; cost++) {
                    int ways = dp[j][b][cost];
                    if (ways == 0) continue;
                    int new_cost = cost + extra;

                    auto add = [&](int blocks, int ends, int choices) {
                        if (choices <= 0) return;
                        int &target = next[blocks][ends][new_cost];
                        target = (target + 1LL * ways * choices) % MOD;
                    };

                    add(j + 1, b, j + 1 - b); // 新建普通块。
                    add(j, b, 2 * j - b);     // 接在一个开放边界。
                    add(j - 1, b, j - 1);     // 合并相邻两块。
                    if (b < 2) {
                        add(j + 1, b + 1, 2 - b); // 新建块并占最终端点。
                        add(j, b + 1, 2 - b);     // 延长最外侧块并占端点。
                    }
                }
            }
        }
        dp.swap(next);
    }

    int ans = 0;
    for (int cost = 0; cost <= limit; cost++) {
        ans = (ans + dp[1][2][cost]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

每层有 O(nL)O(nL) 个状态,每个状态至多五种转移,共 nn 层。时间复杂度为 O(n2L)O(n^2L),额外空间为 O(nL)O(nL)。乘法使用 long long,取模后存回 int。

4.5 样例分析

输入:
4 10
3 6 2 9

输出:
6

六种合法排列为 [2,3,6,9]、[2,3,9,6]、[3,2,6,9] 及它们的逆序,费用分别为 7、10、8。

边界可用以下情况核对:单元素只有一种排列,费用为 0;两个不同元素有两种排列,费用均为两数之差;L<an−a1L<a_n-a_1 时答案为 0,因为任意排列都必须连接最小值与最大值。

5 模型边界

  • 块的顺序:本篇维护有序块,只合并相邻块。换成无序块集合后,必须重新计算选择系数。
  • 最终端点:固定首尾时,端点是否已出现、所在块以及可连接方向可能影响转移,需要补充信息。
  • 额外局部限制:若禁止某些具体元素相邻,仅记块数未必足够,还可能需要边界元素等信息。
  • 重复权值:本题高度互异,每个插入值可唯一识别。允许相同权值时,需区分元素是否有编号,检查计数是否重复。
  • 最优化目标:若要求最小代价,可以对同一状态取最小值;但只有后续费用也由该状态确定时,合并历史才安全。

6 推荐练习

题目 训练目标
[[[p: luogu-P9197 P9197:摩天大楼]]]
[[[p: luogu-P5999 P5999:[CEOI2016] Kangaroo]]]
CSES 1075:Counting Permutations 禁止相邻元素差为 1,练习判断块数是否充分。还需处理与刚插入值相关的边界信息,也可研究容斥解法。
[[[p: codeforces-704B CF704B:Ant Man]]]

这些题附加的限制不同,不能直接套用摩天大楼的五个系数。先说明状态为何充分,再推导转移。

7 思考练习

7.1 练习一:合并系数

当前有序块为 [A] | [B] | [C]。为何不能直接选择 A、C,用新元素将它们合并?

参考分析

块间左右顺序已固定,B 仍位于 A、C 之间。直接合并 A、C 会改变该顺序。只能选择 A 与 B,或 B 与 C,共 j−1=2j-1=2 种。

7.2 练习二:费用先后

处理高度差 ai+1−aia_{i+1}-a_i 时,为何必须用插入前的开放边界数?

参考分析

在这段高度差中,低侧元素恰好是前 ii 个数,跨越它的边由第 ii 层的块决定。插入 ai+1a_{i+1} 后得到的边界数,适用于下一段高度差。用更新后的块数会漏计或多计连接当前高度的边。

7.3 练习三:提前封闭

还有元素未处理,却已得到一个块且两端均为最终端点。这个状态为何不能继续?

参考分析

不能在块内插数,也不能扩展已封闭的两端,或在它们外侧新建块,因此没有合法后继。只有全部元素处理完时,它才是完成的排列。

8 参考资料

9 相关题解

暂无相关题解