← 返回题目列表

Codeforces · 1525/D

D. 扶手椅

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

有$$$n$$$扶手椅,从左到右编号为$$$1$$$到$$$n$$$。有些扶手椅有人占用(每张扶手椅最多一个人),有些则不然。占用的扶手椅数量不大于$$$\frac{n}{2}$$$。

出于某种原因,您想告诉人们从扶手椅移到其他椅子上。如果第 $$$i$$$ 个扶手椅已被某人占用,而第 $$$j$$$ 个扶手椅没有被占用,您可以告诉坐在第 $$$i$$$ 个扶手椅上的人移至第 $$$j$$$ 个扶手椅。一个人从第 $$$i$$$ 扶手椅移动到第 $$$j$$$ 扶手椅所需的时间为 $$$|i - j|$$$ 分钟。您可以多次执行此操作,但这些操作必须按顺序完成,即。 e.在您在上次操作中要求移动的人完成移动到目标扶手椅之前,您不能告诉某人移动。

您想要实现以下情况:最初占用的每个座位都必须是空闲的。您需要做的最短时间是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$) — 扶手椅的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$)。 $$$a_i = 1$$$ 表示第 $$$i$$$ 个扶手椅最初被占用,$$$a_i = 0$$$ 表示它最初是空闲的。占用的扶手椅数量最多为 $$$\frac{n}{2}$$$。

输出

打印一个整数 — 达到以下情况所需花费的最少分钟数:最初占用的每个座位都必须是空闲的。

示例

输入 #1

7
1 0 0 1 0 0 1

输出 #1

3

输入 #2

6
1 1 1 0 0 0

输出 #2

9

输入 #3

5
0 0 0 0 0

输出 #3

0

注意

在第一个测试中,您可以执行以下序列:

1.要求一个人从扶手椅$$$1$$$移到扶手椅$$$2$$$,需要$$$1$$$分钟;
2. 让一个人从扶手椅 $$$7$$$ 移到扶手椅 $$$6$$$,需要 $$$1$$$ 分钟;
3. 要求一个人从扶手椅 $$$4$$$ 移到扶手椅 $$$5$$$,需要 $$$1$$$ 分钟。

在第二个测试中,您可以执行以下序列:

1. 要求一个人从扶手椅 $$$1$$$ 移到扶手椅 $$$4$$$,需要 $$$3$$$ 分钟;
2. 要求一个人从扶手椅 $$$2$$$ 移到扶手椅 $$$6$$$,需要 $$$4$$$ 分钟;
3. 让一个人从扶手椅 $$$4$$$ 移到扶手椅 $$$5$$$,需要 $$$1$$$ 分钟;
4. 让一个人从扶手椅 $$$3$$$ 移到扶手椅 $$$4$$$,需要 $$$1$$$ 分钟。

第三次测试中,没有座位,所以你的目标立即达到。