编程兔 pj T3 题解

__vector__ · 2022-05-23 23:06:33 · 个人记录

前言：

谢 lhx 大佬的思路

记录思路区：

可以使用分组背包，将 a_i,0,-a_i 分成一个组 可以遍历 -\sum a_i \rightarrow \sum a_i 的每个数，对其中每个数进行分组背包求解方案数。
由于遍历的过程复杂度是 O(\sum a_i)，对每个数分组背包求解方案数的过程是 3 \cdot n = O(n) 的（3 是每个组的大小），所以总复杂度是 O(n \cdot \sum a_i + q)

UPD: 实际上上面的复杂度假了，因为分组背包的复杂度不是 O(n)，下面写上我的新想法：
和上面一样，仍然将 a_i,0,-a_i 分成一个组，这样就有了 n 个组，然后遍历这 n 个组，对于每个组遍历 \sum a_i \rightarrow -\sum a_i（要凑成的数）计算方案数。
这样总复杂度是 O(n \cdot \sum a_i + q)
现在的瓶颈是我不会这种计算方案数类型的背包 dp。

做法

还没想好