← 返回题目列表

Codeforces · 1420/E

E. 战斗旅鼠

中文机器翻译题面 查看原题

灯塔守护者彼得指挥一支由 $$$n$$$ 战斗旅鼠组成的军队。他命令他的军队站成一排,并从左到右对旅鼠进行编号,从 $$$1$$$ 到 $$$n$$$。有些旅鼠拿着盾牌。每只旅鼠不能持有超过一个盾牌。

彼得的军队受到的保护越多越好。为了计算军队的保护力,他找到了受保护的旅鼠对的数量,即一对旅鼠中的两只旅鼠都没有持有盾牌,但其中有一只旅鼠之间有盾牌。

现在是时候做好防御准备,增加军队的防护了。为此,彼得可以发出命令。他选择了一只带盾牌的旅鼠,并给了他以下两个命令之一:

- 将盾牌交给左邻居(如果存在且没有盾牌);
- 将盾牌交给正确的邻居(如果存在且没有盾牌)。

彼得在一秒钟内可以准确地发出一个命令。

目前尚不清楚彼得在辩护之前有多少时间。因此,他决定确定从 $$$0$$$ 到 $$$\frac{n(n-1)}2$$$ 的每个 $$$k$$$ 的军队保护最大值,前提是他发出的命令不超过 $$$k$$$。帮助彼得算一下吧!

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 80$$$),即彼得军队中旅鼠的数量。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \le a_i \le 1$$$)。如果 $$$a_i = 1$$$,则第 $$$i$$$ 个旅鼠有盾牌,否则 $$$a_i = 0$$$。

输出

打印 $$$\frac{n(n-1)}2 + 1$$$ 数字,在不超过 $$$0, 1, \dots, \frac{n(n-1)}2$$$ 订单后提供最大可能的保护。

示例

输入 #1

5
1 0 0 0 1

输出 #1

0 2 3 3 3 3 3 3 3 3 3

输入 #2

12
0 0 0 0 1 1 1 1 0 1 1 0

输出 #2

9 12 13 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15

注意

考虑第一个例子。

保护最初等于零,因为对于每对没有盾牌的旅鼠来说,没有带有盾牌的旅鼠。

一秒钟内,彼得可以命令第一只旅鼠将他的盾牌交给右边的邻居。在这种情况下,保护是两次,因为有两对受保护的旅鼠,$$$(1, 3)$$$ 和 $$$(1, 4)$$$。

两秒钟后,Peter 可以按以下方式操作。首先,他命令第五只旅鼠给左边的邻居一个盾牌。然后,他命令第一只旅鼠给右边的邻居一个盾牌。在本例中,彼得有三对受保护的旅鼠 — $$$(1, 3)$$$、$$$(1, 5)$$$ 和 $$$(3, 5)$$$。

您可以确保不可能以保护大于三的方式发出命令。