P14568 【MX-S12-T3】排列 题解 / 连续段 DP 学习笔记 2

zrl123456 · 2025-11-25 22:27:32 · 题解

:::::info[题目基本信息] 考察：动态规划 DP（个人认为是紫，也可能是我太菜了）。
题目简介：
给定 \{op_n\}，值域为 \{0,1,2,3\}，问有多少 n 阶排列满足（对 998244353 取模）：

• \displaystyle\forall i\in(1,n],op_i=0\Rightarrow a_i<\min_{j=1}^{i-1}a_j
• \displaystyle\forall i\in(1,n],op_i=1\Rightarrow a_i>\max_{j=1}^{i-1}a_j
• \displaystyle\forall i\in[1,n),op_i=2\Rightarrow a_i<\min_{j=i+1}^na_j
• \displaystyle\forall i\in[1,n),op_i=3\Rightarrow a_i>\max_{j=i+1}^na_j

数据范围：

• 1\le n\le 5000
• \forall i\in[1,n],op_i\in\{0,1,2,3\}

  ::::: 对于排列，套路地上连续段 DP，套路地设 f_{i,j} 表示考虑到 a_{pos}\in[1,i] 的所有 pos，它们形成了 j 个连续段，至于状态细节不必管，反正最后我尝试的状态都寄了。
  那咋办？！？！？！
  :::::info{open} 不只尝试改变连续段的定义，还要尝试改变连续段定义于的对象。谁告诉你连续段 DP 只能对值域 DP 的？
  切记 DP 题不是套板子题。
  如果你看不懂下面的内容就在心里默念：连续段 DP 是在相对位置上进行 DP，并手玩验证每一种方案都能构造出实例。 ::::: 尝试改变状态的定义，设 f_{i,j} 为考虑到 [1,i] 的所有 pos，未被考虑的位置可以在 j 个值域连续段（中间没有已填位置的段）填，先判掉无解情况（存在一个 2 位于 0 左边或者存在一个 3 位于 1 左边），接下来分类讨论：

• 这时该元素不会对后面的元素造成影响，还会凭空增加一个连续段，所以 DP 数组会整体平移。
• 这时手玩发现这个位置左右至少有一边位置不能填了，这样会使连续段数量变少（可以不变），所以 DP 数组会整体求后缀和。

按上述简单实现可以通过。
时间复杂度为 \Theta(n^2)，空间复杂度为 \Theta(n)。

code