#P4565. [Haoi2016]字符合并

    ID: 2027 传统题 1000ms 256MiB 尝试: 825 已通过: 290 难度: 7 上传者: 标签>CF2300提高+/省选-区间 DP状压 DP状态维度消除枚举最后一次操作区间及合并类DP

[Haoi2016]字符合并

题目描述

有一个长度为 nn 的 01 串,你可以每次将相邻的 kk 个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分数由这 kk 个字符确定。你需要求出你能获得的最大分数。

输入格式

第一行两个整数 n,kn,k。接下来一行长度为 nn 的01串,表示初始串。
接下来 2k2^k 行,每行一个字符 cic_i 和一个整数 wiw_i,cic_i 表示长度为 kk 的 01 串连成二进制后按从小到大顺序得到的第 ii 种合并方案得到的新字符,wiw_i 表示对应的第 ii 种方案对应获得的分数。

输出格式

输出一个整数表示答案

3 2
101
1 10
1 10
0 20
1 30
40

样例解释

第 33 行到第 66 行表示长度为 22 的 44 种 01 串合并方案:
00→1\texttt{00} \rightarrow \texttt{1},得 1010 分;
01→1\texttt{01} \rightarrow \texttt{1},得 1010 分;
10→0\texttt{10} \rightarrow \texttt{0},得 2020 分;
11→1\texttt{11} \rightarrow \texttt{1},得 3030 分。

数据规模与约定

对于 100%100\% 的数据,1≤n≤3001 \leq n \leq 300,2≤k≤82\le k\le8,ci∈{0,1}c_i\in\{0,1\},1≤wi≤1091\le w_i\le10^9。

题目来源