笔者水平有限，如果有错误，欢迎指正。
看到数据范围，很直接的想到 dp，而且 dp 的状态一定有一维用于存储混乱度大小。
正常线性 dp 无法方便地维护混乱度，考虑拆开式子，转化成方便维护的东西。
首先把 从小到大排序，拆掉绝对值。
这里有一个朴素的想法：依次插入每个 ，考虑它的贡献。
因为排过序，所有已经插入的数都 ，没有插入的数都 。此时的贡献为：
-
若当前没有数与它相邻，不位于最终序列两端，贡献为 。因为在最终序列里，它相邻的两个数都比它大。
-
若当前没有数与它相邻，位于最终序列两端，贡献为 。因为在最终序列里，它只有一个相邻的数，这个数比它大。
-
若当前有 个数与它相邻，不位于最终序列两端，贡献为 。
-
若当前有 个数与它相邻，位于最终序列两端，贡献为 。
-
若当前有 个数与它相邻，贡献为 。显然不可能位于序列两端。
的贡献只与它和几个数相邻有关。
于是我们就有了一个状态， 表示已经插入了 个数、形成了 个连续段、有 个连续段的端点位于最终序列两端、已经产生的贡献为 的方案数。可以理解为这 个数任意排序，并划分成满足 和 这两个条件的 个连续段的方案数。
显然答案为 。
转移有 种情况：
-
单独成段，不在最终序列两端，。
-
单独成段，在最终序列两端，。
-
有 个数与它相邻，不位于最终序列两端，。
-
有 个数与它相邻，位于最终序列两端，。
-
有 个数与它相邻，显然不可能位于序列两端，。
注意转移过程中贡献 可能变小，甚至为负数，而且最坏情况 是 量级的，因此这一维需要开 而且需要整体平移。如果改为从大到小插入可以省去整体平移。时空复杂度 。滚动数组压缩掉 这一维后，空间复杂度 。
考虑更优的拆贡献方式，使得 只能递增，。
每一项 会对答案产生贡献，当且仅当 。
在更改拆贡献方式后，我们继续使用原来的 dp 的状态， 表示已经插入了 个数、形成了 个连续段、有 个连续段的端点位于最终序列两端、已经产生的贡献为 的方案数。
容易发现，插入第 个数之后，令 加入 的贡献，这一项恰好贡献了 次。因为此时任意连续段的左右端点，只要不在最终序列的两端，都是满足贡献条件的。
因此转移方程变成：
-
单独成段，不在最终序列两端，。
-
单独成段，在最终序列两端，。
-
有 个数与它相邻，不位于最终序列两端，。
-
有 个数与它相邻，位于最终序列两端，。
-
有 个数与它相邻，显然不可能位于序列两端，。
于是 只会变大，这一维是 量级的。时空复杂度 。滚动数组压缩掉 这一维后，空间复杂度 。
#include<bits/stdc++.h>
using namespace std;
const int NR = 100, LR = 1000;
const int mod = 1e9 + 7;
int n, L, ans, h[NR + 5], dp[2][NR + 5][3][LR + 5];
void Add(int &x, int y) {
x += y;
if(x >= mod) x -= mod;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> L;
if(n == 1) {
cout << "1\n";
return 0;
}
for(int i = 1; i <= n; i++)
cin >> h[i];
sort(h + 1, h + n + 1);
dp[0][0][0][0] = 1;
for(int i = 1; i <= n; i++) {
int d = i & 1;
for(int j = 0; j <= i; j++)
for(int k = 0; k <= 2; k++)
for(int t = 0; t <= L; t++)
dp[d][j][k][t] = 0;
for(int j = 1; j <= i; j++)
for(int k = 0; k <= 2; k++)
for(int t = 0; t <= L; t++) {
int lst = i == n ? t : t - (h[i + 1] - h[i]) * (2 * j - k);
if(lst < 0) continue;
Add(dp[d][j][k][t], 1ll * dp[d ^ 1][j - 1][k][lst] * (j - k) % mod);
if(k > 0) Add(dp[d][j][k][t], 1ll * dp[d ^ 1][j - 1][k - 1][lst] * (3 - k) % mod);
Add(dp[d][j][k][t], 1ll * dp[d ^ 1][j][k][lst] * (2 * j - k) % mod);
if(k > 0) Add(dp[d][j][k][t], 1ll * dp[d ^ 1][j][k - 1][lst] * (3 - k) % mod);
Add(dp[d][j][k][t], 1ll * dp[d ^ 1][j + 1][k][lst] * j % mod);
}
}
for(int i = 0; i <= L; i++)
Add(ans, dp[n & 1][1][2][i]);
cout << ans << '\n';
return 0;
}
共 1 条回复
相当的强👍