33OJ
登录 注册

#P2560. [AHOI2002] Kitty 猫基因突变

    ID: 3377 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>2002各省省选安徽

[AHOI2002] Kitty 猫基因突变

题目描述

学习完基础生物基因学之后,小可可再接再厉,又接着选修了生物基因工程学。小可可至今还清楚地记得学习基础生物基因学的时候,教授提出的 ABC 编码方案是不断地按照

$$T(s) = \begin{cases} \texttt A & \text{若 }s\text{ 串全是 }0 \\ \texttt B & \text{若 }s\text{ 串全是 }1 \\ \texttt C T(s_1) T(s_2) & \text{否则把 }s\text{ 串分成两个等长的子串 }s_1\text{ 和 }s_2 \end{cases}$$

对 Kitty 猫基因 01 串表达式 ss 进行改写,直至最终被改写成只含有字符 A\texttt A、B\texttt B、C\texttt C 的符号串。

学习过程中,小可可协助教授做了一些基因突变育种的工作。但是实验过程中,小可可越来越佩服教授先前提出的基因编码方案,因为恰好基因 ABC 编码的长度说明了 Kitty 猫的品种优良程度,其 ABC 编码长度越短,品种越优良。

教授有一套神秘的技术手段让 Kitty 猫基因的各个位置上的基因单元都能够单独地发生突变;但是技术手段还不足够先进,每次实验都恰好使 ww 个基因单元 00 同时突变成基因单元 11,而基因单元 11 不论在什么位置都不可能发生突变。

教授考察了各种不同的 Kitty 猫,发现 Super Samuel 星球上原有的各种 Kitty 猫的基因中都至少有 ww 个基因单元 00。

而且经研究发现:在不同的位置上发生突变的成本 cic_i 是不同的,而基因 ss 变成 s′s' 的成本 C(s,s′)C(s,s') 就是发生突变的那些基因单元的突变成本的总和。

同时,由于实验室经费不足,教授没有足够的经费来培育出 ww 个基因单元 00 同时发生突变所能得到的最优良品种。为此,他只能以粗略地以突变成本 C(s,s′)+C(s,s')+ 突变后基因的 ABC 编码长度 T(s′)T(s') 为评价指标 A(s,s′)A(s,s') 来确定将培育出的新品种,A(s,s′)A(s,s') 越小,其评价效果越好。教授总是培育出评价效果最好的那些突变品种。

例如,k=3k=3,即 ss 串长度为 232^3;c1c_1、c2c_2、⋯\cdots、cnc_n 依次是 1010、1010、55、66、33、22、11、22;w=2w=2,即恰好每次都是 22 个基因单元 00 同时发生突变。此时基因的 01 串表达式 s=11000101s=11000101 中的第三、四、五和第七个基因单元都是 00。

有一种突变方案是第三个和第四个基因单元发生突变,突变后基因的 01 串表达式 sI′=11110101s_\textrm I'=11110101。因此其突变成本 C(s,sI′)=c3+c4=5+6=11C(s,s_\textrm I')=c_3+c_4=5+6=11;其 ABC 编码 T(sI′)=CBCCABCABT(s_\textrm I')=\texttt{CBCCABCAB},编码长度是 99。所以突变后得到的新品种的评价指标值 A(s,sI′)=11+9=20A(s,s_\textrm I')=11+9=20。

另外一种突变方案是第五个和第七个基因单元发生突变,突变后基因的 01 串表达式 sII′=11001111s_\textrm{II}'=11001111。因此其突变成本 C(s,sII′)=c5+c7=3+1=4C(s,s_\textrm{II}')=c_5+c_7=3+1=4;其 ABC 编码 T(sII′)=CCBABT(s_\textrm{II}')=\texttt{CCBAB},编码长度是 55。所以突变后得到的新品种的评价指标值 A(s,sII′)=4+5=9A(s,s_\textrm{II}')=4+5=9。

显然后一种方案的评价效果要比前一种方案好。

经过计算,同时突变两个基因单元的各种方案中评价效果最好的方案就是同时突变第五个和第七个基因单元的方案。

现在请你编写程序帮小可找出评价效果最好的突变方案。

输入格式

文件中第一行有两个正整数 kk 和 ww,1≤k≤71\le k \le 7,1≤w≤301\le w \le 30;第二行存放的是长度为 2k2^k 的基因 01 串表达式;第三行有 2k2^k 个整数,依次为突变成本 c1c_1、c2c_2、⋯\cdots、c2kc_{2^k},1≤ci≤1001\le c_i \le 100。

输出格式

以一行的形式输出评价效果最好的突变方案的评价指标。

3 2
11000101
10 10 5 6 3 2 1 2
9