P9197 [JOI Open 2016] 摩天大楼 / Skyscraper 题解 / 连续段 DP 学习笔记

zrl123456 · 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 和 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。
把两个原有连续段合并成了一个连续段：
都合并连续段了，那位置肯定不位于 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 又双叒叕要成立。
新建了一个连续段：
还是要分两种情况讨论。
- 扫到的点位置不位于位置 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;

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