P9197 [JOI Open 2016] 摩天大楼 - 题解

· · 题解

广告：笔者的《浅谈一类转移过程中依赖已插入元素的具体信息的序列计数问题 - 连续段 dp》

注意到绝对值求和的形式，因此考虑将权值 a 排序以规避绝对值。下文默认 a 已按从小到大排序，且插入元素的顺序亦为从小到大。

记当前所有相邻项的绝对值之和为 k，当我们在两个已有相邻项之间插入新元素 a_i 时，经过尝试我们发现新的 k 值依赖于已有元素的具体取值。让我们重点考虑一下在端点处插入的情况，表面上我们需要知道端点元素的值 x 并令 k \gets k + a_i - x，但是事实上，由于对于一个单调递增的序列 b，其相邻项间绝对值之和 = \sum b_i - b_{i - 1} = b_n - b_1，这意味着，如果新插入的元素不是连续段的边界（如果一个端点被称为“边界”，则这个端点处不会再有新的元素插入），我们可以暂时忽略这个元素对 k 的贡献，利用作为连续段边界的元素来统一处理这些贡献。

比较容易发现，每个未经过合并的连续段都是一个单谷序列（即 \exists k \in [1, n], a_i > a_{i + 1} \forall i \in [1, k - 1] , a_i < a_{i + 1} \forall i \in [k, n - 1]），如果确定了连续段的左右边界，并知道连续段中的最小元素（称这个最小元素的位置为“中间”），则这个连续段相邻项间的绝对值之和 = 右边界元素的值 - 中间元素的值 + 左边界元素的值 - 中间元素的值。我们将这三种贡献拆开，作为独立的三部分分别考虑：

这样一来，我们完成了关于 k 的转移。因此记 f_{i, j, k, d} 表示考虑了前 i 个元素，形成了 j 个连续段，贡献和为 k，已存在 d 个边界（此处及下文的“边界”意为“被强行插入到最左端 / 最右端的边界”），满足以上约束的方案数。我们可以按如下方式写出状态转移方程：

最终答案为 Ans = \sum \limits_{i = 0} ^ {L} f_{n, 1, i, 2}。

然而，分析一下时间复杂度，记 V 表示 a_i 的值域，则 k 这一维的状态数会达到 \mathcal{O}(nV)，总复杂度 \mathcal{O}(n ^ 3V)，对于本题是一个错误的复杂度。

瓶颈在哪里呢？前面提到 k 的状态数达到 \mathcal{O}(nV)，但是事实上最终统计答案时有用的状态数仅是 \mathcal{O}(L) 的。但是，按照我们 dp 的分析过程，这 \mathcal{O}(nV) 个状态是不能直接省去的，因为 k 在转移过程中可增可减，可以达到 \mathcal{O}(nV) 的状态数。是否能换一种角度考虑贡献，使得贡献的转移只增不减，从而能够尽可能地去除无用状态呢？

考虑一种差分的思想：\forall i < j, a_j - a_i = \sum \limits_{k = i} ^ {j - 1} a_{k + 1} - a_k，则此时 a_{k + 1} - a_k 对总贡献的贡献为所有贡献中满足 i \leq k < j 的 a_j - a_i 数量。

形式化一下，记 b 为对 a 进行任意重排列后的序列，g(i) 表示 b_i 这个数值在 a 中的位置（\text{i.e. } a_{g(i)} = b_i）。显然总贡献即 \sum b_{i + 1} - b_i = \sum a_{g(i + 1)} - a_{g(i)}，记 x_i = \min(g(i), g(i + 1)), y_i = \max(g(i), g(i + 1))，依据上文差分的方法可以将总贡献写作 \sum a_{y_i} - a_{x_i} = \sum \sum \limits_{k = x_i}^{y_i - 1}a_{k + 1} - a_k，因此可以说明 a_{k + 1} - a_k 对总贡献的贡献为满足 x_i \leq k < y_i 的 (x_i, y_i) 数量，也即前述结论。

它其实就是个差分。但是从贡献的角度考虑也能归为一种叫微元贡献法的 trick。其本质为，面对多个不同的贡献，但我们可以用若干个微元组合出所有不同贡献时，可以考虑此类微元贡献法。

由于上文提到 a_{k + 1} - a_k 对总贡献的贡献为所有贡献中满足 i \leq k < j 的 a_j - a_i 数量，而我们插入元素的顺序是从小到大，因此此后在每个连续段的两个端点处插入的新元素，都一定且仅能构成 1 次这样的 i \leq k < j。（“一定”是因为连续段的端点处一定会插入新的值，“仅能”是因为插入新的值后新的值一定会大于 a_k，无法再组成新的 i \leq k < j。)

由于确定一个边界后无法再向边界处插入新元素/连续段，因此边界的数量会降低此后新元素对总贡献的增量，仍然需要单独记录边界的数量 d。

设计 dp 状态为 f_{i, j, k, d}，意为考虑 a 中前 i 个元素构成了 j 个连续段，当前总贡献为 k，边界数量为 d 的方案数。综上，当我们插入一个新数 a_{i + 1} 时，新的总贡献 k' = k + (a_{i + 1} - a_i) \times (2j - d)，并且可以直接忽略 k' > L 的无用状态。

最后，考虑连续段 dp 的几种转移即可。记 k' \gets k + (a_{i + 1} - a_i) \times (2j - d)。当我们插入 a_{i + 1} 时，

答案显然为 Ans = \sum \limits_{i = 0} ^ {L} f_{n, 1, i, 2}。

值得一提的是，上文提及的两种 dp 方法中，k 都并非仅考虑 a 中这前 i 个元素互相之间的总贡献，而是提前计算了这些元素之后所能产生的一切贡献，从而规避了后效性。这里也分享一篇介绍这种贡献提前计算的好文。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 100 + 10, MOD = 1e9 + 7, M = 1000 + 10;
inline void pl(int &x, i64 y) {x = (y + x) % MOD;}

int f[N][N][M][3], a[N];

void solve(){
    int n, l; cin >> n >> l;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    f[0][0][0][0] = 1;
    for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++)
        for(int k = 0; k <= l; k++) for(int d = 0; d < 3; d++){
            i64 p = k + (a[i + 1] - a[i]) * (2 * j - d), t = f[i][j][k][d];
            if(!t) continue;
            if(p > l) continue;

            pl(f[i + 1][j + 1][p][d], t * (j + 1 - d));
            if(j >= 2) pl(f[i + 1][j - 1][p][d], t * (j - 1));
            if(j >= 1) pl(f[i + 1][j][p][d], t * (2 * j - d));
            if(d < 2) pl(f[i + 1][j + 1][p][d + 1], t * (2 - d));
            if(d < 2 && j >= 1) pl(f[i + 1][j][p][d + 1], t * (2 - d));
        }
    int ans = 0;
    for(int i = 0; i <= l; i++)
        pl(ans, f[n][1][i][2]);
    cout << (n == 1 ? 1 : ans) << "\n";
}

UPD 2023.11.18: 感谢 @Missa 指出的一些细节错误。