#CW66. 电车站(tram)
电车站(tram)
题目描述
有 种服务。每个车站用一个长度为 的二进制字符串表示;第 位为 表示提供第 种服务,为 表示不提供。所有长度为 的二进制字符串都对应一个车站。
两个车站之间可以双向行驶,当且仅当它们的编码恰好有一位不同,其他各位完全相同。一次行驶只能沿这样的一条线路从一个车站到另一个车站,可以连续行驶多次。
第 种服务的费用为 。到达编码为 的车站时,需要支付该车站所提供的所有服务的费用之和;起点车站不收费,同一个车站若被多次到达,每次到达都要收费。求从起点编码 到终点编码 的最小总费用。若 ,答案为 。
输入格式
从 tram.in 文件中读入。
第一行包含整数 以及两个长度均为 的二进制字符串 ,满足 。
第二行包含 个整数 ,其中 ,表示第 种服务的费用。
输出格式
从 tram.out 文件中输出。
输出一个整数,表示从 到 的最小总费用。
样例 1 输入
3 111 010
4 15 8
样例 1 输出
31
样例 1 解释
一种最优走法是 :
- 到达 支付 ;
- 到达 支付 ;
- 到达 支付 ;
- 到达 支付 。
合计 并不是最优;把顺序调整为 中的中间状态取舍后,最小费用为 (例如 的某个等价走法,通过先在便宜状态间往返、最后一次性付清昂贵位)。可以证明不存在费用低于 的走法。
样例 2 输入
4 0000 1111
1 2 3 4
样例 2 输出
20
数据范围
所有输入满足 ; 都是长度恰为 且只含 0、1 的字符串;每个服务费用满足 。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 15 | ||
| 2 | 20 | ||
| 3 | 25 | 与 的公共 1 位数不超过 |
|
| 4 | 40 | 无额外限制, |