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

输入 #1

4 5
1 2 3 4

输出 #1

1
2
1
1
1

输入输出样例 #2

输入 #2

1 5
3

输出 #2

-1
-1
0
-1
-1

输入输出样例 #3

输入 #3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

输出 #3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1

说明/提示

限制条件

• $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 翻译