← 返回题目列表

Codeforces · 1040/A

A. 回文舞

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

一群 $$$n$$$ 舞者正在为闭幕式排练表演。舞者们排成一排,他们已经研究好了舞步,不能改变姿势。对于其中一些人来说,已经购买了白色的舞蹈服,对于其中一些人来说是黑色的,而对于其余的人,该服装将在将来购买。

买套装的那天,导演被告知,如果现场的套装颜色能够形成回文,那么奥运会的参赛者就会很高兴。回文是从左到右读取和从右到左读取时相同的序列。导演喜欢这个主意,她想购买服装,使最左边的舞者的衣服颜色与最右边的舞者的衣服颜色相同,左第二个与右第二个相同,依此类推。

导演知道买一套白色西装需要多少节,买一套黑色西装需要多少节。你需要找出是否可以购买西装来形成回文,如果可以,这样做的最低成本是多少。请记住,舞者不能改变位置,并且由于官僚原因,不允许为已有服装的舞者购买新服装,即使这会减少总体支出。

输入

第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \leq n \leq 20$$$, $$$1 \leq a, b \leq 100$$$) — 舞者数量、白色套装的成本和黑色套装的成本。

下一行包含$$$n$$$数字$$$c_i$$$,其中$$$i$$$-表示第$$$i$$$个舞者的套装颜色。数字 $$$0$$$ 表示白色,$$$1$$$ — 黑色,$$$2$$$ 表示该舞者的套装仍有待购买。

输出

如果不交换舞者并为有舞者购买新套装就不可能形成回文,则输出-1。否则,输出最小的价格以获得想要的视觉效果。

示例

输入 #1

5 100 1
0 1 2 1 2

输出 #1

101

输入 #2

3 10 12
1 2 0

输出 #2

-1

输入 #3

3 12 1
0 1 0

输出 #3

0

注意

在第一个示例中,获得回文颜色的最便宜的方法是为左边第三个舞者购买黑色套装,为最右边的舞者购买白色套装。

在第二个示例中,最左边的舞者服装已经与最右边的舞者服装不同,因此无法获得所需的颜色。

在第三个示例中,所有套装都已购买,并且它们的颜色形成回文。