#CW66. 电车站(tram)

电车站(tram)

题目描述

有 nn 种服务。每个车站用一个长度为 nn 的二进制字符串表示;第 ii 位为 11 表示提供第 ii 种服务,为 00 表示不提供。所有长度为 nn 的二进制字符串都对应一个车站。

两个车站之间可以双向行驶,当且仅当它们的编码恰好有一位不同,其他各位完全相同。一次行驶只能沿这样的一条线路从一个车站到另一个车站,可以连续行驶多次。

第 ii 种服务的费用为 cic_i。到达编码为 vv 的车站时,需要支付该车站所提供的所有服务的费用之和;起点车站不收费,同一个车站若被多次到达,每次到达都要收费。求从起点编码 ss 到终点编码 ee 的最小总费用。若 s=es=e,答案为 00。

输入格式

从 tram.in 文件中读入。

第一行包含整数 nn 以及两个长度均为 nn 的二进制字符串 s,es,e,满足 1≤n≤10001\le n\le 1000。

第二行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\dots,c_n,其中 1≤ci≤1061\le c_i\le 10^6,表示第 ii 种服务的费用。

输出格式

从 tram.out 文件中输出。

输出一个整数,表示从 ss 到 ee 的最小总费用。

样例 1 输入

3 111 010
4 15 8

样例 1 输出

31

样例 1 解释

一种最优走法是 111→101→001→000→010111\to101\to001\to000\to010:

  • 到达 101101 支付 c1+c3=12c_1+c_3=12;
  • 到达 001001 支付 c3=8c_3=8;
  • 到达 000000 支付 00;
  • 到达 010010 支付 c2=15c_2=15。

合计 12+8+0+15=3512+8+0+15=35 并不是最优;把顺序调整为 111→101→001→000→010111\to101\to001\to000\to010 中的中间状态取舍后,最小费用为 3131(例如 111→101→001→000→010111\to101\to001\to000\to010 的某个等价走法,通过先在便宜状态间往返、最后一次性付清昂贵位)。可以证明不存在费用低于 3131 的走法。

样例 2 输入

4 0000 1111
1 2 3 4

样例 2 输出

20

数据范围

所有输入满足 1≤n≤10001\le n\le 1000;s,es,e 都是长度恰为 nn 且只含 0、1 的字符串;每个服务费用满足 1≤ci≤1061\le c_i\le 10^6。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 15 1∼51\sim 5 n≤20n\le 20
2 20 6∼106\sim 10 n≤200n\le 200
3 25 11∼1511\sim 15 ss 与 ee 的公共 1 位数不超过 2020
4 40 16∼2016\sim 20 无额外限制,1≤n≤10001\le n\le 1000