分数: 500 点
问题陈述
给你一个整数数组 A=(a_1,a_2,\ldots,a_N).
您可以执行以下操作任意次数(可能为零)。
- 选择一个非空连续子数组 A,并将其从数组中删除。
对于每个 x=1,2,\ldots,M,解决以下问题:
- 找到使元素之和的最小可能操作数 A 等于 x。
如果不可能求出元素之和 A 等于 x,打印
-1。
请注意,空数组的元素总和为 0.
约束
- 1 \leq N,M \leq 3000
- 1 \leq a_i \leq 3000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M a_1 \ldots a_N
输出
打印 M 行。的 i- 第行应包含以下问题的答案 x=i.
示例输入 1
4 5 1 2 3 4
示例输出 1
1 2 1 1 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.
示例输入 2
1 5 3
示例输出 2
-1 -1 0 -1 -1
示例输入 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