/ Vijos / 题库 /

火柴游戏

火柴游戏

描述

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

图片

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

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

每种操作都有一定的代价:
1, 对一个添加操作,如果这是第ii次进行添加操作,这一步的费用为p1i+q1p_1*i+q_1
2, 对一个删除操作,如果这是第ii次进行删除操作,这一步的费用为p2i+q2p_2*i+q_2
3, 对一个移动操作,如果这是第ii次进行移动操作,这一步的费用为p3i+q3p_3*i+q_3

例如,小明在游戏中添加了3根火柴,移动了1根火柴,删除了2根火柴,那么他总的花费为[(p11+q1)+(p12+q1)+(p13+q1)]+(p31+q3)+[(p21+q2)+(p22+q2)][( 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 的非负整数p1p_1,q1 q_1,p2 p_2,q2 q_2,p3 p_3,q3 q_3

输出格式

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

样例1

样例输入1

2
46
78
0 1 0 1 0 1

样例输出1

样例2

样例输入2

2
23
52
1 1 1 1 1 1

样例输出2

限制

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

来源

SHTSC 2012 Day1

信息

ID
1854
难度
7
分类
(无)
标签
递交数
78
已通过
16
通过率
21%
被复制
1
上传者