本篇讨论排列构造中的连通块DP,也称插入DP:按数值顺序处理元素,记录它们在最终排列中形成的片段,再通过新建、延长、合并片段完成构造。
连续段DP 在顺序固定的序列上维护结尾状态;本篇需要构造排列,处理顺序与最终位置顺序不同。阅读前需掌握基础DP、全排列 和 排列与组合。
1 按值插入
给定
另一种顺序是先排序,按
但这些数在最终排列中未必相邻。例如,最终排列为:
最终排列: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] 是不同状态。竖线表示尚待填充的间隔,不是已经相邻。
若当前有
| 操作 | 结构示意 | 块数变化 |
|---|---|---|
| 新建 | `[A] | [x] |
| 延长 | `[A x] | [B]或[A] |
| 合并 | [A x B] |
其中
2 基础计数
先不加任何费用和位置限制,用所有排列检验状态与系数。
2.1 状态定义
令
初始化
2.2 转移系数
从一个有
- 新建块:可放在最左、最右或相邻块之间,共
个位置。 - 延长块:每块左右各有一个边界,共
种选择。 - 合并块:相邻块之间有
个间隔,选择一个放入新元素,共 种。
因此:
不能把最后一个系数换成任意两块的选择数:本状态已固定左右顺序,只有相邻两块能被新元素直接连接。若采用无序路径集合等其他状态定义,系数需要重新推导。
2.3 不重不漏
删除新加入的最大元素,根据它在块中有零个、一个或两个邻居,分别还原为新建、延长或合并前的唯一配置。因此三类转移不重不漏。
块数足以决定上述操作的数量,块内具体数值不会改变系数,故可以把不同配置按块数汇总。
2.4 手算示例
| 已处理元素数 |
||||
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 |
| 2 | 2 | 2 | 0 | 0 |
| 3 | 6 | 12 | 6 | 0 |
| 4 | 24 | 72 | 72 | 24 |
全部元素处理完后,只接受一个块,得到
还可用
3 端点限制
最终排列有左、右两个端点。若某个已处理元素被指定占据最终端点,就不能再向它外侧接数,也不能在它外侧新建块。
维护
3.1 开放边界
只保存块数不够:一个块两端都开放时,后续可继续延长;两端都占据最终端点时,整条排列已经封闭,不能再放剩余元素。
3.2 端点转移
新元素可以不占最终端点,也可以占一个尚未确定的最终端点。已存在其他元素时,它不可能同时占据两端。
| 操作 | 新块数 | 新端点数 | 系数 |
|---|---|---|---|
| 新建普通块 | |||
| 延长普通边界 | |||
| 合并相邻两块 | |||
| 新建块,并占一个最终端点 | |||
| 延长最外侧块,并占一个最终端点 |
前两项排除已封闭的边界或外侧位置。后两项只能发生在尚未占据的左端、右端,各提供一种选择;仅在
例如左端未占据时,既可在所有块左侧新建 [x] 并指定它为最终左端,也可将
按
当
4 摩天大楼
题目:luogu P9197: P9197:[JOI Open 2016] 摩天大楼。
将
原题范围为
4.1 高度差贡献
设已经处理到
在最终排列中,每条连接低处与高处的相邻边,都会在这个高度差上贡献
因此,跨过本次高度差时,费用增加:
例如排序高度为 [5, 2, 9]。处理完高度 5 后有一个块 [5, 2],左端已占据,故
更早的高度差
这是将边长按高度差拆开累计。每条边被它跨越的各段高度差各计一次,总和仍是原边长。费用状态不必保存每条开放边的另一端是谁。
4.2 状态与转移
定义
从第
- 用插入前的
计算 。 - 若
,舍弃;后续费用非负,不会降回限制内。 - 按端点转移表的五种操作,更新对应的
:
所有计数均对
4.3 初值与答案
放入最小元素时,还没有跨过高度差,费用为 0:
它可以不占端点、仅占左端或右端、同时占据两端。最后一种情况仅在
最终必须只有一个块,且两个最终端点均已确定:
每个完整排列的端点标记唯一;从它删去较大元素,还能唯一恢复各层的块。因此,这些标记不会重复统计最终排列。
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;
}
每层有 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;两个不同元素有两种排列,费用均为两数之差;
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,共
7.2 练习二:费用先后
处理高度差
参考分析
在这段高度差中,低侧元素恰好是前
7.3 练习三:提前封闭
还有元素未处理,却已得到一个块且两端均为最终端点。这个状态为何不能继续?
参考分析
不能在块内插数,也不能扩展已封闭的两端,或在它们外侧新建块,因此没有合法后继。只有全部元素处理完时,它才是完成的排列。
8 参考资料
9 相关题解
暂无相关题解