自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 21:14:00，当前版本为作者最后更新于2022-04-12 20:12:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：给定 $N$ 个数， 求 $N$ 个数任取 $K$ 个后和在 $[l,r]$ 范围内的方案数。

显然，需要枚举子集，然后进行求和，不过 $O(2^n)$ 的复杂度显然过不了，所以可以进行一些剪枝：剩下的数全选也不到 $l$ 或者当前的和已经超过 $r$ 就不继续枚举。从大到小排序后进行搜索即可。

更快的方法是考虑 DP ，设 $F[i][j]$ 是选了 $1$ ~ $i$ 后，和为 $j$ 的方案总数，那么可以推出 $F[i][j] = F[i-1][j] + F[i-1][j-a[i]]$ ，$i=0$ 或 $j=0$ 时方案数为 $1$ 。

因为上面转移状态的第二维 $j$ 每次都是从比 $j$ 小的状态转移过来，且第一维 $i$ 只跟 $i-1$ 有关，所以我们可以使用滚动数组存储，省略第一维 $i$ 并倒着枚举 $j$ ，就可以不重复地统计方案了。