#PQJ579x8606. QOJ 579_8606

    ID: 3012 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HAOI 2016

QOJ 579_8606

1.字符合并

【问题描述】 有一个长度为n 的01 串,你可以每次将相邻的k 个字符合并, 得到一个新的字符并获得一定分数。得到的新字符和分数由这k 个 字符确定。你需要求出你能获得的最大分数。 【输入格式】 第一行两个整数n,k。 接下来一行长度为n 的01 串,表示初始串。 接下来2k行,每行一个字符ci和一个整数wi,ci表示长度为k 的01 串连成二进制后按从小到大顺序得到的第i 种合并方案得到的 新字符, wi表示对应的第i 种方案对应获得的分数。 【输出格式】 输出一个整数表示答案。 【样例输入】 3 2 101 1 10 1 10 0 20 1 30 【样例输出】 40

【样例说明】 第3 行到第6 行表示长度为2 的4 种01 串合并方案。00->1, 得10 分,01->1 得10 分,10->0 得20 分,11->1 得30 分。 【数据范围】 数据编号 n k wi 0 =10 2 <=10 5 1 =15 3 <=10 5 2 =20 4 <=10 5 3 =25 5 <=10 5 4 <=50 5 <=10 6 5 <=50 6 <=10 6 6 <=50 7 <=10 6 7 <=50 8 <=10 6 8 <=100 3 <=10 7 9 <=100 4 <=10 7 10 <=100 5 <=10 7 11 <=100 6 <=10 7 12 <=200 5 <=10 8 13 <=200 6 <=10 8 14 <=200 7 <=10 8 15 <=200 8 <=10 8 16 <=300 5 <=10 9 17 <=300 6 <=10 9 18 <=300 7 <=10 9 19 <=300 8 <=10 9 对于100%的数据,n>=1,0<=ci<=1,wi>=1