本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-01 10:05:25

:::info[题目基本信息] 考察：动态规划 DP。
题目简介：
给定一个两两元素不同的序列 $\{a_n\}$，现在问对其任意重排成 $\{a'n\}$，使得 $\displaystyle\sum{i=2}^n|a_i-a_{i-1}|\le m$ 的方案数对 $10^9+7$ 取模的结果。
时间限制 2s，空间限制 512MB。
数据范围：

• $1\le n\le 100$
• $1\le m\le 1000$
• $\forall i\in[1,n],1\le a_i\le 1000$ ::: :::info[闲话] 我咋不会这个套路，还是太菜了。
  ::: 先考虑暴力 DP，然后我们发现暴力 DP 做不了。状压 DP 状态是 $\Theta(2^nm)$ 量级的，其它可能的暴力 DP 就算是多项式复杂度，次数也非常高，这条路走不通。
  所以我们要采用连续段 DP。 ::::success[连续段 DP] :::info[注] 连续段 DP 这个名字是我自己起的，还可以叫它插入 DP 之类，没有一个明确的术语。
  ::: 注意到这个题画出图直观表示是这个样子的：
  
  现在我们用一条直线从下往上扫：
  
  连续段 DP 就记录扫到了哪里，同时记录直线下方部分构成了几个连续段进行 DP。
  :::: 好的，对于这道题就是要让折线竖直方向长度不超过 $m$，所以我们先暂时设 $f_{i,j,k}$ 表示从下往上扫到了 $i$ 个点，形成了 $j$ 个连续段，直线下方折线竖直方向总长度为 $k$ 的方案数。
  但是有一些问题，在中间位置的点往上会贡献两条折线，在位置 $1$ 或 $n$ 上的点只会往上贡献一条折线，所以我们还要记录扫到了几个位于位置 $1$ 和 $n$ 的点。
  所以我们最终状态就设 $f_{i,j,k,l}$ 表示从下往上扫到了 $i$ 个点，形成了 $j$ 个连续段，直线下方竖直方向折线总长度为 $k$，扫到了 $l$ 个位于位置 $1$ 和 $n$ 上的点，状态数是 $n\times n\times m\times 3=\Theta(n^2m)$ 的，看上去很对，空间如果有点炸用滚动数组压掉第一维就行了。

接下来，考虑转移。
这时会有一个问题，看图：

注意到未被扫到的点下一个扫到谁的贡献是不一样的，所以我们考虑进行大力分讨（这里就是为什么本题填表法严格劣于刷表法，可是我还是写了填表法）：

1. 连在了一个原有连续段上：
   这时还需要分是不是扫到了一个位于位置 $1$ 和 $n$ 的分类讨论。
   • 扫到的点位置不位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(2j-l)f_{i-1,j,k-(2j-l)(a_i-a_{i-1}),l}$$ 前提条件：首先 $(2j-l)(a_i-a_{i-1})$ 这一坨肯定要大于等于 $0$ 且小于等于 $k$（下同，下文中省略），然后还需要原本就有连续段，也就是 $j\ne 0$。
   • 扫到的点位置位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(3-l)f_{i-1,j,k-(2j+1-l)(a_i-a_{i-1}),l-1}$$ 前提条件：首先原本要有连续段，即 $j\ne 0$，同时 $l\ne 0$。
2. 把两个原有连续段合并成了一个连续段：
   都合并连续段了，那位置肯定不位于 $1$ 或 $n$ 了啊。
   这时转移方程式为：
   $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+jf_{i-1,j+1,k-(2j+2-l)(a_i-a_{i-1}),l}$$ 前提条件：合并完后肯定不能没有连续段，所以 $j\ne 0$ 又双叒叕要成立。
3. 新建了一个连续段：
   还是要分两种情况讨论。
   • 扫到的点位置不位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(j-l)f_{i-1,j-1,k-(2j-2-l)(a_i-a_{i-1}),l}$$ 前提条件：都出现 $j-1$ 了那么肯定 $j\ne 0$ 啊。
   • 扫到的点位置位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(3-l)f_{i-1,j-1,k-(2j-1-l)(a_i-a_{i-1}),l-1}$$ 前提条件：同上，需要满足 $j\ne 0$ 且 $l\ne 0$。

好的我们终于分讨完了，最后答案就等于：
$$\sum_{k=0}^mf_{n,1,k,2}$$ 时空复杂度均为 $\Theta(n^2m)$，时间常数可能有些爆炸。
:::warning[坑点] 主要还是说明为什么填表法不如刷表法。

填表法和刷表法虽然状态转移方程式同样要分 $5$ 种情况讨论，但是刷表法中 $k$ 的变化量是一样的，而填表法并不，所以如果你写填表法你会写出来这么一个鬼东西：

if(j&&((j<<1)-l)*(a[i]-a[i-1])>=0&&((j<<1)-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j][k-((j<<1)-l)*(a[i]-a[i-1])][l]*((j<<1)-l)%MOD)%=MOD;
if(j&&l&&((j<<1)+1-l)*(a[i]-a[i-1])>=0&&((j<<1)+1-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j][k-((j<<1)+1-l)*(a[i]-a[i-1])][l-1]*(3-l)%MOD)%=MOD;
if(j&&((j+1<<1)-l)*(a[i]-a[i-1])>=0&&((j+1<<1)-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j+1][k-((j+1<<1)-l)*(a[i]-a[i-1])][l]*j%MOD)%=MOD;
if(j&&((j-1<<1)-l)*(a[i]-a[i-1])>=0&&((j-1<<1)-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j-1][k-((j-1<<1)-l)*(a[i]-a[i-1])][l]*(j-l)%MOD)%=MOD;
if(j&&l&&((j-1<<1)+1-l)*(a[i]-a[i-1])>=0&&((j-1<<1)+1-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j-1][k-((j-1<<1)+1-l)*(a[i]-a[i-1])][l-1]*(3-l)%MOD)%=MOD; 

可读性很低，不建议写。
:::