P5215 [SHOI2014] 神秘金字塔

ForgotMe · 2024-08-03 15:48:53 · 题解

不算难的一道状态压缩 dp 题。

首先这个题面就很抽象，非要说得那么复杂。

手玩一下样例可以发现，这个金字塔可以分成完全相同的 4 部分，只需要考虑其中一部分就可以了。

将其形式化一下就是有一个二维数组 a，满足

• \sum_{i=1}^h \sum_{j=1}^{l_i}a_{i,j}=n

对所有可能的 a 计数，其中 l_1,h\le 10，n\le 250，l_1\ge l_2\ge ... \ge l_h。

直接做确实不太行，突破点在于 l_1 很小，发现所有可能的 a 的第一行状态全部搜出来，只有 48620 种。

于是考虑状压 dp，设 f_{i,S,j} 表示到了第 i 行，当前状态为 S，当前 a 的总和为 j 的方案数。

转移的话非常简单，枚举当前行的状态 S，上一行的状态 T，看能不能转移。可惜直接来的话最坏枚举次数达到了 48620^2。

注意到能转移的条件本质上是一个高维的包含关系，使用高维后缀和优化即可。

有一些细节需要注意：由于一个合法的状态满足数单调不增，按照正常的高维后缀和写法可能会出现一些问题，例如二维情况下 (0,0) 与 (1,1)，按理来说是 (1,1) 先转移到 (0,1) 最后转移到 (0,0)。但是 (0,1) 这个状态是不合法的，可能不存在导致贡献统计错误，于是需要进行修正。当高维前缀和进行到第 i 维时，如果是从不合法的状态转移而来，需要将该状态进行修正，即如果前面存在比第 i 个数小的数，滚一遍后缀 max 即可。例如 (0,1) 就直接修正成 (1,1)。