学习：连续端 dp。
目标：最优化 \(F(S) = \sum_{i=1}^{n-1} w(A_{S_i}, A_{S_{i+1}})\)，或者说，重排序列以最优化相邻两个元素产生的贡献。
考虑拆开贡献，拆成类似 \(L(a_i) + R(a_{i+1})\) 的形式。连续端 dp 通过以下两个操作生成作为一整个连续端的序列：
- 在一个段的左或右插入一个元素
- 新建一个段
- 用一个元素合并两个段
通过拆分贡献，我们可以在插入或合并时不知道两边的元素以计算对答案的贡献。
这样的好处是，我们可以变换枚举答案的顺序，来拆分两个元素间的贡献，从而使插入贡献与两边元素，进而可以快速计算。
在 P9197 中，通过从大到小枚举元素，绝对值函数的符号被确定，从而拆分了贡献。
这样过不去，需要“微元法”。我不大清楚怎么想到这个做法，从拆贡献的角度勉强可以。
把 \(w(l, r)\) 表示成 \(\sum w(i, i+1)\)？这里的下标都在扫描线扫的东西上。
可以看成扫描线，扫值域，dp 统计连续段。
挺有趣。
卡空间，卡 \(n=1\)。
我好抽象啊。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
void add(int &x, int y) { if ((x += y) >= mod) x -= mod; }
int mul(int x, int y) { return 1ll * x * y % mod; }
int main() {
int n, l; scanf("%d %d", &n, &l);
if (n == 1) return printf("1\n"), 0;
// std::vector f(n, std::vector (n + 1, std::vector (l + 1, std::vector<int> (3))));
std::vector<int> a(n);
for (int &u : a) scanf("%d", &u);
std::sort(a.begin(), a.end());
std::vector c(n + 1, std::vector (l + 1, std::vector<int> (3)));
auto f = c;
f[1][0][0] = 1, f[1][0][1] = 2;
for (int i = n - 1; i; i--) {
auto g = c;
for (int j = 1; j <= n - i; j++)
for (int k = 0; k <= l; k++) {
for (int d = 0; d < 3; d++) {
int t = (2 * j - d) * (a[i] - a[i - 1]);
if (k + t > l) continue;
add(g[j + 1][k + t][d], mul(f[j][k][d], j + 1 - d));
if (d < 2) add(g[j + 1][k + t][d + 1], mul(f[j][k][d], 2 - d));
if (j >= 2) add(g[j - 1][k + t][d], mul(f[j][k][d], j - 1));
add(g[j][k + t][d], mul(f[j][k][d], 2 * j - d));
if (d < 2) add(g[j][k + t][d + 1], mul(f[j][k][d], 2 - d));
}
}
f = g;
}
int ans = 0;
for (int i = 0; i <= l; i++)
add(ans, f[1][i][2]);
printf("%d\n", ans);
return 0;
}