/ Vijos / 题库 /

火柴游戏

火柴游戏

描述

小明非常喜欢玩火柴游戏:首先用棒摆出一个可能是错误的等式,然后通过添加、删除或移动火柴棒,使得等式成立。下图展示每个数字的样子。

图片

我们只考虑形如 A = B 的式子,其中A和B是两个具有相同位数的整数。小明可进行三种操作:
1. 在任意位置添加一根火柴棒;
2. 从任意位置删除一根火柴棒;
3. 将任意一根火柴棒移动到另个位置。

在完成所有操作后,等号两侧必须都是合法的数字且全相。我们约定:
1: 小明不能消除任何数字,也就是说可以删一个的部分火柴但不能令它消失;
2: 小明不能增加任何数字,也就是说可以在一个已有的数字上添加火柴, 或将火柴移动到一个已有的数字上,但不能凭空增加;
3: 小明不能拆分或者合并数字,比如将一个8变成两个1,或者将两个1合并成一个 8;
4: 其中代表1的火柴棒必须靠右边摆放,在左不是有效数字。

每种操作都有一定的代价:
1, 对一个添加操作,如果这是第\(i\)次进行添加操作,这一步的费用为\(p_1*i+q_1\)
2, 对一个删除操作,如果这是第\(i\)次进行删除操作,这一步的费用为\(p_2*i+q_2\)
3, 对一个移动操作,如果这是第\(i\)次进行移动操作,这一步的费用为\(p_3*i+q_3\)

例如,小明在游戏中添加了3根火柴,移动了1根火柴,删除了2根火柴,那么他总的花费为\([( p_1*1+q_1)+(p_1*2+q1)+(p_1*3+q_1)]+(p_3*1+q_3)+[(p2*1+q_2)+(p_2*2+q_2)]\)。

小明想知道,他如何才能用最少的花费使等式成立。你写个程序帮助吗

格式

输入格式

第1 行,一个整数L,表示等式中两个数的位数。
第2-3 行,每行各一个长度为L、仅由数字构成的字符串,表示等式两侧的数。
第4 行,给出六个不超过100 的非负整数\(p_1\),\( q_1\),\( p_2\),\( q_2\),\( p_3\),\( q_3\)。

输出格式

输出一行 ,包含 一个整数,为使等式成立的最小的操作代价。

样例1

样例输入1

2
46
78
0 1 0 1 0 1

样例输出1

2

样例2

样例输入2

2
23
52
1 1 1 1 1 1

样例输出2

9

限制

对于 30% 数据,有 L ≤ 20 ,且 p1 = p2 = p3 = 0= 0;
对于 60% 数据,有 L ≤ 100;
对于 100% 数据,有 L ≤ 200 。

来源

SHTSC 2012 Day1

信息

ID
1854
难度
7
分类
(无)
标签
递交数
54
已通过
9
通过率
17%
上传者