题意回顾

我们有 $N$ 根柱子，高度为 $h_i$，可以任意排列。对于每个排列，计算它能接住的雨水量（类似“接雨水”问题），要求输出所有可能的雨水量（从小到大）。

核心思路

1. 接雨水量的另一种计算方式

对于给定的排列，接雨水量有一个重要性质：

[ \text{雨水量} = \sum_{i=1}^n \min(\text{左边最高}, \text{右边最高}) - h_i ]

但这里作者用了一个更巧妙的转化：

雨水量 = 所有柱子形成的矩形面积 - 柱子总面积

其中矩形面积 = 排列长度 × 最高柱高度，但这里作者实际上是用差分的思想来处理的。

2. 关键观察

作者发现：如果我们按高度从大到小排序柱子，那么雨水量的可能值可以通过动态规划来枚举。

定义状态：

• $dp[len][s]$ 表示使用前若干根柱子，当前“长度”为 $len$，某种“面积和”为 $s$ 是否可行

3. 算法流程解析

sort(h + 1, h + n + 1, greater<int>());
dp[1][h[1]] = 1;

• 柱子按高度降序排序
• 初始化：第一根柱子，长度为1，某种“面积”为 $h[1]$

L(i, 2, n) {
    bitset<S> Or;
    L(len, i - 1, n) {
        Or |= dp[len] << ((n - len) * h[i]);
        dp[len] = Or >> ((n - len) * h[i]);
    }
    dp[i - 1].reset();
}

这是最核心的部分：

• 对于第 $i$ 根柱子（高度 $h[i]$）
• 考虑它插入到已有排列的最左端或最右端
• (n - len) * h[i] 这个偏移量实际上是在计算新增的雨水面积
• 通过 bitset 的移位操作来高效更新状态

int sum = accumulate(h + 1, h + n + 1, 0);
dp[n] >>= sum;

• 计算柱子总面积
• 最后通过右移来得到实际的雨水量

4. 状态定义的具体含义

实际上，作者的状态设计很巧妙：

• $dp[len][s]$ 中的 $s$ 表示某种“累计值”
• 最终雨水量 = $(s - \text{柱子总面积})$ 的某种线性组合
• 通过排序和偏移量的设计，确保能枚举所有可能的雨水量

复杂度分析

• 排序：$O(n \log n)$
• DP 转移：$O(n^2 \cdot \frac{S}{w})$，其中 $w$ 是 bitset 的位宽（约 64）
• 空间：$O(n \cdot S)$，但用 bitset 压缩后实际很小
• 由于 $n \leq 500$, $h_i \leq 50$，$S = n \times V = 500 \times 51 = 25500$，可以通过

举例验证

对于样例1：1 5 2 1 4

排序后：5 4 2 1 1

程序会枚举所有可能的雨水量：0 1 2 3 4 5 6 8

总结

这个解法的精妙之处在于：

1. 将接雨水问题转化为面积计算问题
2. 利用排序简化状态转移
3. 使用 bitset 高效处理大规模状态枚举
4. 通过巧妙的偏移量设计避免重复计算

是一个典型的组合优化 + 位运算优化的高效解法。