红绿塔 题解

思路

最大高度 $h$ 是满足 $h(h+1)/2\le r+g$ 的最大整数。把第 $i$ 层染成红色等价于从 $1,2,\ldots,h$ 中选择数 $i$，红色积木总数就是所选数字之和。

记 $S=h(h+1)/2$。若红色用量为 $x$，绿色用量为 $S-x$，合法条件是

因此问题转化为统计集合 $\{1,2,\ldots,h\}$ 中元素和落在该区间的子集数量。

做法

子任务 1 枚举 $2^h$ 个子集并统计合法者。

子任务 2 使用二维 0/1 背包，$dp_{i,x}$ 表示只考虑前 $i$ 层、红色用量为 $x$ 的方案数。

完整做法把二维 DP 压缩为一维。按层数从小到大枚举，并将红色用量从大到小更新，保证每层恰好使用一次。最后对合法区间求和。

复杂度

子任务 1 的时间复杂度为 $O(2^h h)$。子任务 2 的时间和空间复杂度分别为 $O(hr)$ 与 $O(hr)$。完整做法的时间复杂度为 $O(hr)$，空间复杂度为 $O(r)$。