[JOI Open 2016] 摩天大楼

JOI Open 2016 摩天大楼

标签

插入/连续段 DP

设 \(S = | f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N|\)

因为 \(S\) 内的元素只跟相邻两项相关，考虑插入 DP。

考虑对于现在序列的两个相邻的数，以后有没有新的 \(a_i\) 插入是有巨大影响的（符号都变了），所以是需要维护若干个连续段的。

先将 \(a\) 从小到大排序，去掉绝对值。接着依次插入 \(a_i\)。

设 \(f(i, j, l)\) 表示插入了前 \(i\) 个数，有 \(j\) 个连续段，当前的 \(S = l\) 的方案数。（\(S\) 为当前确定的项的总和，即连续段内部的差值之和）。然后插入 \(a_i\)，结果傻眼了，因为我们不知道 \(a_i\) 左右两边的是啥，算出来 \(l'\)。

这时我们可以用一个经典的小 trick，只动态维护 \(\le a_i\) 的折线之和。如下图，我们把 \(f\) 丢到一个平面上，则红色折线的总长度就是答案。

而我们只需要维护 \(\le a_i\) 的折现之和即可。（下图中蓝色的部分。）

而加入 \(a_{i + 1}\) 后，只需要加入下图中绿色的部分即可。

这绿色的部分每一段都的长度都是 \(a_{i + 1} - a_i\)。而有多少段绿色呢？不难发现相邻的连续段之间都有 \(2\) 段（上去一段，下来一段）。图中有 \(3\) 个连续段，绿段有 \(2 \times (3 - 1) = 4\) 段。

但是需要注意，可能当前最后一个连续段后面还有连续段（如下图），这时绿段又会多一个。同理，当前第一个连续段前面也可能还有连续段，也会影响绿段的数量。

所以我们的 DP 状态要拓展为 \(f(i, j, l, k = 0/1/2)\)，最后一维表示最前面、最后面是否还有连续段（因为是一样的，记个数量即可。）

平时的连续段 DP，转移分三种：自己新建一段/插到某个段的开头/结尾/插到两个段中间，使得他们合并。

对于没有 \(k\) 不改变的情况，这三种都存在。而对于改变 \(k\) 的情况（就是 \(k + 1\) 的情况）只有两种：

• 自己新建一段在开头/结尾。（1）
• 插入到开头那个段的开头/结尾那个段的结尾。（2）

总是就是这个新加入的数必须在整个序列的头/尾。否则如果后面都没有数插到头/尾，这种情况可能会被算重。（因为这和 \(k\) 不变是完全一样的。）

转移时 \(l' = l + (a_i - a_{i -1})(2j - k)\)，使 \(k\) 增加时要乘一个 \(2 - k\) 的系数。（可能又两种选择）

初始状态：\(f(1, 1, 0, 0) = f(1, 1, 0, 2) = 1, f(1, 1, 0, 1) = 2\)，目标状态：\(f(n, 1, l, 0)(l \le L)\)。

时间复杂度：\(O(n^2L)\)。

最后附上转移式子：

int v = dp[p][j][l][c]; dp[p][j][l][c] = 0; // c 是上文中的 k，从 i - 1 转移到 i（滚动了）
if (!v) continue;
int nl = l + (a[i] - a[i - 1]) * (2 * j - c);
if (nl > m) continue;
// Plus(u, v, k) 表示 u += v * k
Plus(dp[q][j][nl][c], v, 2 * j - c); // 插入到某段的开头/结尾
Plus(dp[q][j + 1][nl][c], v, j + 1 - c); // 自成一段
Plus(dp[q][j - 1][nl][c], v, j - 1); // 使合并两段
if (c < 2) {Plus(dp[q][j][nl][c + 1], v, 2 - c); // (2)Plus(dp[q][j + 1][nl][c + 1], v, 2 - c); // (1)
}

总结

运用了一个动态维护 \(\le a_i\) 折线长度的小 trick，还是很神奇的。

最初以为使 \(k + 1\) 的转移也是三种都可以，然后被狠狠地坑了一把。提醒我们要多造点极端小样例。

转移还是比较恶心的。