「JOI Open 2016」摩天大楼 - 题解

注意到绝对值求和的形式，比较自然地想到将权值 \(a\) 排序以规避绝对值，下文默认 \(a\) 按从小到大排序，且插入元素的顺序亦为从小到大。

考虑一种差分的思想：\(\forall i < j, |a_j - a_i| = 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 被总结为微元贡献法。事实上，本题若不使用这种方法，每一组相互独立的 \(|b_y - b_x|\) 的值难以被维护，换言之，当我们从小到大添加元素时，插入项对总贡献的增量是难以被维护和计算的（建议理解下文 dp 思想后再尝试理解这句话）。一般而言，面对贡献难以被单独维护时会考虑微元贡献法。

考虑连续段 dp 的标准形式，记两维 \(i, j\) 表示已考虑 \(a\) 中前 \(i\) 个数被划分为了 \(j\) 个连续段。对于本题，注意到 \(L\) 的限制，比较自然地想到记一维 \(k\) 表示总贡献。

首先要考虑的问题是，当我们插入一个新数 \(a_{i + 1}\) 时，总贡献 \(k\) 的变化。比较容易发现单独计算 \(a_{i + 1}\) 的贡献是不现实的，因为它牵扯到了相邻元素的值，且后续计算中还可能继续产生贡献。这就是我们使用微元贡献法的原因了，由于上文提到“\(a_{k + 1} - a_k\) 对总贡献的贡献为所有贡献中满足 \(i \leq k < j\) 的 \(|a_j - a_i|\) 数量”，而我们插入元素的顺序是从小到大，因此此后在每个连续段的两个边界处插入的新元素，都一定且仅能构成 \(1\) 次这样的 \(i \leq k < j\)。

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

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

其实这里的 \(k\) 并非仅考虑 \(a\) 中前 \(i\) 个元素的总贡献，而是提前计算了元素此后会产生的贡献，从而规避了后效性。任务安排便是这种思想的例题之一。

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

• 作为一个新的连续段插入到不为边界的间隙中，即 \(f_{i + 1, j + 1, k', d} \gets f_{i, j, k, d} \times (j + 1 - d)\)
• \((j \geq 2)\)作为中间点合并两个连续段，即 \(f_{i + 1, j - 1, k', d} \gets f_{i, j, k, d} \times (j - 1)\)
• \((j \geq 1)\)作为一个新元素插入到某个连续段的非边界端点处，即 \(f_{i + 1, j, k', d} \gets f_{i, j, k, d} \times (2j - d)\)
• \((d < 2)\)作为一个新的连续段作为边界插入，即 \(f_{i + 1, j + 1, k', d + 1} \gets f_{i, j, k, d} \times (2 - d)\)
• \((d < 2)\)作为一个新元素作为边界端点插入到某个连续段，即 \(f_{i + 1, j, k', d + 1} \gets f_{i, j, k, d} \times (2 - d)\)

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

\(\tt Code\)

#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(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) 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";
}