自动搬运

查看原文

来自洛谷，原作者为

	ForgotMe 花与剑无痕，高挂一轮明灯。银蝶染旧梦，生死莫再问。

搬运于2025-08-24 22:08:20，当前版本为作者最后更新于2024-08-03 15:48:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

• $\forall 1\le i\le h$，$a_{i,1}=l_i$。

• $\forall 1\le i\le h,2\le j\le l_i$，$1\le a_{i,j}\le \min(a_{i-1,j},a_{i,j-1})$。

• $\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)$。