AT_abc275_f [ABC275F] Erase Subarrays

给定一个正整数序列 $A=(a_1,a_2,\ldots,a_N)$。 你可以重复进行如下操作任意次（包括 $0$ 次）： - 从 $A$ 中选择一个（非空的）连续子序列并将其删除。 对于 $x=1,2,\ldots,M$，请解决以下问题： - 求将 $A$ 的元素总和恰好变为 $x$ 所需的最小操作次数。如果无论如何操作都无法使 $A$ 的元素总和恰好变为 $x$，则输出 $-1$。 另外，当 $A$ 为空时，$A$ 的元素总和视为 $0$。

输入以如下格式从标准输入给出。 > $N$ $M$ $a_1$ $\ldots$ $a_N$

输出 $M$ 行。第 $i$ 行输出对应 $x=i$ 的答案。

## 限制条件 - $1 \leq N, M \leq 3000$ - $1 \leq a_i \leq 3000$ - 输入均为整数 ## 样例解释 1 以下给出使操作次数最小的操作示例。 - 对于 $x=1$，对 $a_2,a_3,a_4$ 进行操作后，$A$ 的元素总和变为 $x$。 - 对于 $x=2$，先对 $a_3,a_4$ 进行操作，再对 $a_1$ 进行操作后，$A$ 的元素总和变为 $x$。 - 对于 $x=3$，对 $a_3,a_4$ 进行操作后，$A$ 的元素总和变为 $x$。 - 对于 $x=4$，对 $a_1,a_2,a_3$ 进行操作后，$A$ 的元素总和变为 $x$。 - 对于 $x=5$，对 $a_2,a_3$ 进行操作后，$A$ 的元素总和变为 $x$。 由 ChatGPT 4.1 翻译