B3624 背包统计方案

Usada_Pekora · 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 ，就可以不重复地统计方案了。