连续段DP

· · 算法·理论

对于一类与排列数量计数有关，或转移中需要与相邻插入元素有关的 DP。

通常情况下，对于排列计数问题，我们要确定一个插入元素的顺序，并将插入的元素按如下方式操作：

  1. 构成新的一段
  2. 加入某一段的开头或结尾
  3. 连接两段

Phoenix and Computers

设 dp_{i,j} 表示打开了 i 台电脑，并形成了 j 段。

根据上述方式转移：

  1. 新建段：dp_{i+1,j+1}\leftarrow dp_{i,j}\times (j + 1)
  2. 加入某一段：dp_{i+1,j}\leftarrow dp_{i,j}\times 2 \times j,dp_{i+2,j}\leftarrow dp_{i,j}\times 2\times j
  3. 合并块：dp_{i+2,j-1} \leftarrow dp_{i,j}\times2\times(j-1),dp_{i+3,j-1} \leftarrow dp_{i,j}\times (j-1) 注意合并块不能有 dp_{i+1,j-1}\leftarrow dp_{i,j}\times(j-1), 因为如果两端相隔 1，中间那个会自动打开，这样会在 3.1 的转移中会算重（感谢 @Zhang_xiangyou 更正）。

Magneti

发现方案数可以根据磁铁的排列方式计算出来，不同的磁铁排列方式影响了磁铁段的最短长度。

先按照 r_i 从小到大排序。

设 dp_{i,j,k} 表示考虑前 i 个磁铁，分成了 j 段，长度为 k。

  1. 新建段：dp_{i+1,j+1,k+1}\leftarrow dp_{i,j,k}\times(j+1)

  2. 加入某一段：dp_{i+1,j,k+r_{i+1}}\leftarrow dp_{i,j,k}\times 2\times j

  3. 合并块：dp_{i+1,j-1,k+r_{i+1}+r_{i+1}-1}\leftarrow dp_{i,j,k}\times (j-1)

[JOI Open 2016] 摩天大楼

给你一个数列 a，求随机排列 a 后，令 f=|a_2-a_1|+|a_3-a_2|+...+|a_n-a_{n-1}|，求 f\leq L 的方案数。

把 (i,a_i) 拍到平面上，从上往下扫描，f 可以表示为所有相邻点间的纵坐标之差的和。

显然，把直线往下平移一个单位后，增加的 f（纵坐标之差）为 (a_i-a_{i-1}))\times T \times 2，T 为平移前段数（若有一段在开头或结尾，则贡献要减1，所以要确定已选段中是否有开头结尾）。因此定义状态 dp_{i,j,k,p(0/1),q(0/1)}。

转移大概长这样：

int t = a[i] - a[i + 1];
(dp[i + 1][j + 1][k + 2 * (j) * t][0][0] += dp[i][j][k][0][0] * (j + 1)) %= mod;//建新段
(dp[i + 1][j + 1][k + (2 * (j) - 1) * t][1][0] += dp[i][j][k][1][0] * j) %= mod;//建新段
(dp[i + 1][j + 1][k + (2 * (j) - 1) * t][0][1] += dp[i][j][k][0][1] * j) %= mod;//建新段
(dp[i + 1][j + 1][k + (2 * (j) - 2) * t][1][1] += dp[i][j][k][1][1] * (j - 1)) %= mod;//建新段

(dp[i + 1][j][k + 2 * j * t][0][0] += dp[i][j][k][0][0] * 2 * j) %= mod;//加入某段
(dp[i + 1][j][k + (2 * j - 1) * t][1][0] += dp[i][j][k][1][0] * (2 * j - 1)) %= mod;//加入某段
(dp[i + 1][j][k + (2 * j - 1) * t][0][1] += dp[i][j][k][0][1] * (2 * j - 1)) %= mod;//加入某段
(dp[i + 1][j][k + (2 * j - 2) * t][1][1] += dp[i][j][k][1][1] * (2 * j - 2)) %= mod;//加入某段

(dp[i + 1][j - 1][k + 2 * (j) * t][0][0] += dp[i][j][k][0][0] * (j - 1)) %= mod;//连接两段
(dp[i + 1][j - 1][k + (2 * (j) - 1) * t][0][1] += dp[i][j][k][0][1] * (j - 1)) %= mod;//连接两段
(dp[i + 1][j - 1][k + (2 * (j) - 1) * t][1][0] += dp[i][j][k][1][0] * (j - 1)) %= mod;//连接两段
(dp[i + 1][j - 1][k + (2 * (j) - 2) * t][1][1] += dp[i][j][k][1][1] * (j - 1)) %= mod;//连接两段

// 建新段 （开头）
(dp[i + 1][j + 1][k + (2 * (j) - 0) * t][1][0] += dp[i][j][k][0][0]) %= mod;
(dp[i + 1][j + 1][k + (2 * (j) - 1) * t][1][1] += dp[i][j][k][0][1]) %= mod;
// 建新段 （结尾）
(dp[i + 1][j + 1][k + (2 * (j) - 0) * t][0][1] += dp[i][j][k][0][0]) %= mod;
(dp[i + 1][j + 1][k + (2 * (j) - 1) * t][1][1] += dp[i][j][k][1][0]) %= mod;

// 加入某段并成为开头
(dp[i + 1][j][k + (2 * j - 0) * t][1][0] += dp[i][j][k][0][0]) %= mod;
(dp[i + 1][j][k + (2 * j - 1) * t][1][1] += dp[i][j][k][0][1]) %= mod;
// 加入某段并成为结尾
(dp[i + 1][j][k + (2 * j - 0) * t][0][1] += dp[i][j][k][0][0]) %= mod;
(dp[i + 1][j][k + (2 * j - 1) * t][1][1] += dp[i][j][k][1][0]) %= mod;

kangaroo

和上一道题思路，状态类似，但是要简单很多。