CF1420E Battle Lemmings

灯塔看守人 Peter 指挥着一支由 $n$ 只战斗旅鼠组成的军队。他让军队排成一列，并从左到右将旅鼠编号为 $1$ 到 $n$。有些旅鼠手持盾牌，每只旅鼠最多只能持有一面盾牌。 Peter 希望他的军队防护能力越强越好。为了计算军队的防护能力，他会统计被保护的旅鼠对的数量。被保护的旅鼠对指的是：这对旅鼠中的两只都没有盾牌，但它们之间有一只持盾牌的旅鼠。 现在是准备防御的时候，需要提升军队的防护能力。为此，Peter 可以下达命令。他可以选择一只持盾牌的旅鼠，并下达以下两种命令之一： - 如果左边有邻居且该邻居没有盾牌，则将盾牌交给左边的邻居； - 如果右边有邻居且该邻居没有盾牌，则将盾牌交给右边的邻居。 Peter 每秒钟只能下达一条命令。 Peter 不确定自己有多少时间可以准备防御。因此，他想要知道，对于每个 $k$，从 $0$ 到 $\frac{n(n-1)}{2}$，在不超过 $k$ 次命令的情况下，军队防护能力的最大值是多少。请你帮助 Peter 计算出来！

第一行包含一个整数 $n$（$1 \le n \le 80$），表示 Peter 军队中的旅鼠数量。 第二行包含 $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}$ 次命令后，军队防护能力的最大值。

请参考第一个样例。 初始时，防护能力为零，因为对于每一对没有盾牌的旅鼠之间都没有持盾牌的旅鼠。 在一秒内，Peter 可以命令第一只旅鼠将盾牌交给右边的邻居。此时，防护能力为 $2$，因为有两对被保护的旅鼠对，分别是 $(1, 3)$ 和 $(1, 4)$。 在两秒内，Peter 可以这样操作：首先让第五只旅鼠将盾牌交给左边的邻居，然后让第一只旅鼠将盾牌交给右边的邻居。此时，Peter 有三对被保护的旅鼠对，分别是 $(1, 3)$、$(1, 5)$ 和 $(3, 5)$。 你可以验证，无法通过其他命令使防护能力超过 $3$。 由 ChatGPT 4.1 翻译