字符合并

GitHub跳转原题关系图返回列表

利用区间合并后残留长度恒为 (len-1) mod (k-1)+1 这一不变量,把长度不超过 k-1 的残留 01 串整个压进区间 DP 的状态,分割点以 k-1 为步长枚举。

OJ: roj

题目 ID: 1767

难度:提高+/省选-

标签:动态规划区间DP状态压缩python

创建: 2026-10-08 00:09

更新: 2026-10-08 00:09

形式化题目

给定长度为 nn 的 0101 串 a1a2⋯ana_1 a_2 \cdots a_n。一次操作可以任选一段连续的 kk 个字符, 把它们整体替换成 一个新字符,并获得对应的分数:把这 kk 个字符按"最左字符为最高位" 看成一个 kk 位二进制数 ii,查表得到新字符 cic_i 和分数 wiw_i。

求任意次(含 00 次)操作后能获得的最大累计分数。约定 1⩽n⩽3001 \leqslant n \leqslant 300,2⩽k⩽82 \leqslant k \leqslant 8,0⩽ci⩽10 \leqslant c_i \leqslant 1,wi⩾1w_i \geqslant 1。

注意题目不要求把整串合并到某个固定长度:可以随时停手,但 wi⩾1w_i \geqslant 1 说明多做一次合并一定不亏,所以最优解总会把整串合并到不能再合并为止。

正解

思路

朴素做法。 直接搜索:每一步枚举当前串里相邻的 kk 个字符,合并后递归下去。 每一步的分支数是 O(n)O(n),而一次完整合并要做 O(n/(k−1))O(n/(k-1)) 步,搜索树规模呈指数级, n⩾20n \geqslant 20 就彻底跑不动了。

瓶颈在哪? 换成区间 DP 也躲不开同一个问题:只记"区间 [l,r][l,r] 合并后的最大分数" 是不够的,因为后续要和相邻字符拼在一起查表,必须知道这个区间最后变成了什么 0101 串。 于是问题变成:一个区间合并完之后,究竟有多少种可能的形态?

关键观察一:残留长度是不变量。 每次合并把 kk 个字符变成 11 个,序列长度净减少 k−1k-1。所以区间 [l,r][l,r](长度 L=r−l+1L = r-l+1)无论采用什么合并顺序,只要合并到不能再合并, 残留长度都相同:

rest(L)=(L−1) mod (k−1)+1,1⩽rest(L)⩽k−1.\text{rest}(L) = (L-1) \bmod (k-1) + 1, \qquad 1 \leqslant \text{rest}(L) \leqslant k-1 .

L>1L > 1 时该区间能整体塌缩成 11 个字符,当且仅当 L≡1(modk−1)L \equiv 1 \pmod{k-1}(此时 rest=1\text{rest} = 1)。

区间长度 LL 1 2 3 4 5 6 7 8 9 10
残留长度(k=3k=3) 1 2 1 2 1 2 1 2 1 2
残留长度(k=8k=8) 1 2 3 4 5 6 7 1 2 3

读表要点:残留长度只由 L mod (k−1)L \bmod (k-1) 决定,与合并顺序无关;k=8k=8 时每 77 个长度 循环一次,只有 L=1,8,15,…L = 1, 8, 15, \dots 这些长度才可能被整体合成 11 个字符。 又因为 k⩽8k \leqslant 8,残留长度最多 77,残留串的形态最多只有 27=1282^7 = 128 种—— 这个 0101 串可以整个塞进 DP 的状态维里。

关键观察二:分割点只需以 k−1k-1 为步长枚举。 想把 [l,r][l,r] 变成残留串 SS, 可以看成"前缀的残留串 S′S' 再拼上后缀收缩成的 11 个字符":最右那一位来自某个后缀 [mid+1,r][mid+1, r],它必须恰好收成 11 个字符,即 (r−mid−1) mod (k−1)=0(r-mid-1) \bmod (k-1) = 0。 于是分割点只有 mid=r−1, r−1−(k−1), r−1−2(k−1),…mid = r-1,\, r-1-(k-1),\, r-1-2(k-1), \dots,数量降到 L/(k−1)L/(k-1)。

关键观察三:拼满 kk 位就必须合并。 当 rest(L)=1\text{rest}(L) = 1 时, 前缀 [l,mid][l,mid] 恰好残留 k−1k-1 位(L−1≡0(modk−1)L-1 \equiv 0 \pmod{k-1} 推出前缀长度 ≡0(modk−1)\equiv 0 \pmod{k-1},其残留长度就是 k−1k-1),加上后缀的 11 位正好拼出 kk 位, 这一步合并是必须发生的,直接查表加分即可。

状态与转移。 设 f[l][r][S]f[l][r][S] 表示把 al⋯ara_l \cdots a_r 合并到不能再合并、且残留串恰为 SS 时的最大得分;SS 是长度 rest(L)\text{rest}(L) 的二进制数(高位在前,与题面查表顺序一致)。

  • 初始化:f[i][i][ai]=0f[i][i][a_i] = 0,其余全部 −∞-\infty。
  • 转移(按 L=2,3,…,nL = 2, 3, \dots, n 递增):
f[l][r][S′≪1∣b]=max⁡mid(f[l][mid][S′]+f[mid+1][r][b])(rest(L)>1), f[l][r][S' \ll 1 \mid b] = \max_{mid}\Big( f[l][mid][S'] + f[mid+1][r][b] \Big) \qquad (\text{rest}(L) > 1),
f[l][r][cid]=max⁡mid(f[l][mid][S′]+f[mid+1][r][b]+wid),id=S′≪1∣b(rest(L)=1). f[l][r][c_{id}] = \max_{mid}\Big( f[l][mid][S'] + f[mid+1][r][b] + w_{id} \Big), \quad id = S' \ll 1 \mid b \qquad (\text{rest}(L) = 1).
  • 答案:max⁡Sf[1][n][S]\max_S f[1][n][S]。

正确性。 对任意合并方案,最终残留串从左到右的每个字符都对应原来位置的一段连续区间, 这些区间首尾相接铺满 [l,r][l,r];而且没有任何一次合并跨越两段之间的边界(否则那个字符就会 同时含两段的原始位置)。于是各段内部是互相独立的合并过程,最后一段 [mid+1,r][mid+1,r] 恰好 收成 11 个字符,说明它的长度 ≡1(modk−1)\equiv 1 \pmod{k-1},正是转移里枚举的那些 midmid; 若整段收成 11 个字符,则最后一步必然是把拼出来的 kk 位整体合并。 按区间长度归纳可知,转移枚举到了所有合法方案,且转移中的每一步都对应真实的合法操作, 所以 f[1][n][⋅]f[1][n][\cdot] 的最大值就是答案。

样例推演。 样例 n=3n = 3,k=2k = 2,串为 1 0 1,规则表为 00→(1,10)00 \to (1, 10)、01→(1,10)01 \to (1, 10)、10→(0,20)10 \to (0, 20)、11→(1,30)11 \to (1, 30)。 k=2k = 2 时 k−1=1k-1 = 1,每个区间都满足 L≡1(mod1)L \equiv 1 \pmod 1,所以转移一律走"拼满 kk 位就合并" 那条分支。下表列出全部 66 个区间的状态(SS 用二进制写,— 表示 −∞-\infty):

区间 [l,r][l,r] 长度 LL 残留长度 f[⋅][⋅][0]f[\cdot][\cdot][0] f[⋅][⋅][1]f[\cdot][\cdot][1] 说明
[1,1][1,1] 1 1 — 0 基态,残留串 1
[2,2][2,2] 1 1 0 — 基态,残留串 0
[3,3][3,3] 1 1 — 0 基态,残留串 1
[1,2][1,2] 2 1 20 — 合并 10 →0\to 0,得 2020 分
[2,3][2,3] 2 1 — 10 合并 01 →1\to 1,得 1010 分
[1,3][1,3] 3 1 — 40 走 mid=1mid = 1:0+10+w11=400 + 10 + w_{11} = 40

最后一行是关键:mid=2mid = 2 的走法(先合并左边 10)只得到 20+0+10=3020 + 0 + 10 = 30, 而 mid=1mid = 1 的走法(先合并右边 01)得到 0+10+30=400 + 10 + 30 = 40,取最大即答案。 这也说明合并顺序真的会影响结果,不能贪心。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 00:09
# update_at: 2026-10-08 00:09

import sys

NEG = -10 ** 18  # 不可达状态的哨兵;合法得分一定 >= 0

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type States = list[int]           # 某区间残留串各形态(下标即 01 串的值)对应的最大得分
type Rules = list[tuple[int, int]]  # 2^k 条合并规则:二进制值 -> (新字符, 本次分数)


def join(pre: States, suf: States, rules: Rules | None) -> States:
    """把前缀残留串 S 与后缀单字符 b 拼成 S<<1|b;rules 非空表示这次恰好拼满 k 位,立即合并加分。"""
    if rules is None:
        out = [NEG] * (len(pre) * 2)
        for s, base in enumerate(pre):
            if base <= NEG // 2:
                continue                    # 前缀该形态不可达,整条拼法都不成立
            for b, tail in enumerate(suf):
                if tail <= NEG // 2:
                    continue                # 后缀该形态不可达,这条拼法也不成立
                val = base + tail
                if val > out[s << 1 | b]:
                    out[s << 1 | b] = val
        return out
    out = [NEG, NEG]
    for s, base in enumerate(pre):
        if base <= NEG // 2:
            continue
        for b, tail in enumerate(suf):
            if tail <= NEG // 2:
                continue
            ch, score = rules[s << 1 | b]
            if base + tail + score > out[ch]:
                out[ch] = base + tail + score
    return out


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    a = [0] + [next(data) for _ in range(n)]
    rules: Rules = [(next(data), next(data)) for _ in range(1 << k)]

    km1 = k - 1  # 每次合并净减少 k-1 个字符,这就是长度不变量
    # f[l, r]:把 a[l..r] 合并到不能再合并时,残留串各形态对应的最大得分。
    # 残留长度恒为 (r-l) % km1 + 1,所以表长正好是 2 ** 该长度。
    f: dict[tuple[int, int], States] = {}
    for i in range(1, n + 1):
        single = [NEG, NEG]  # 单字符区间只可能残留它自己
        single[a[i]] = 0
        f[i, i] = single

    for length in range(2, n + 1):
        rest = (length - 1) % km1     # 该区间残留长度 = rest + 1
        full = rest == 0              # 残留 1 个字符:这次拼接恰好凑满 k 位,要立即合并
        for l in range(1, n - length + 2):
            r = l + length - 1
            # 后缀 [mid+1, r] 必须以 1 个字符收尾,故 mid 以 k-1 为步长倒着取
            parts = [
                join(f[l, mid], f[mid + 1, r], rules if full else None)
                for mid in range(r - 1, l - 1, -km1)
            ]
            f[l, r] = [max(column) for column in zip(*parts)]

    print(max(f[1, n]))


if __name__ == "__main__":
    solve()

C++ 版(同一算法,用 ll f[305][305][128] 的定长全局数组代替 Python 的稀疏表):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 00:09
 * update_at: 2026-10-08 00:09
 */
// 一本通 1767《字符合并》:[HAOI2016] 字符合并 同源。
// 区间 DP + 状压:区间 [l, r] 无论怎么合并,最终残留长度恒为 (len-1) % (k-1) + 1,
// 而 k <= 8 说明残留串最多 k-1 = 7 位,可以整个塞进状态里。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 305;               // n <= 300,留安全系数
const int MAXK = 8;
const int MAXS = 1 << (MAXK - 1);   // 残留长度 <= k-1 <= 7,故残留串形态最多 2^7 = 128 种

struct Rule {
    int ch;                         // 合并后得到的新字符
    ll score;                       // 本次合并获得的分数
};

int n, k;
int a[MAXN];                        // a[1..n]:初始 01 串
Rule rule[1 << MAXK];               // rule[i]:i 的 k 位二进制(最高位为最左字符)对应的合并规则
// f[l][r][S]:把 a[l..r] 合并到不能再合并、且残留串恰为 S(长度 (r-l) % (k-1) + 1)时的最大得分
ll f[MAXN][MAXN][MAXS];

const ll NEG = -1000000000000000000LL;  // 不可达状态的哨兵;合法得分一定 >= 0

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int tot = 1 << k;
    for (int i = 0; i < tot; i++) scanf("%d%lld", &rule[i].ch, &rule[i].score);

    int km1 = k - 1;                // 每次合并净减少 k-1 个字符,这就是长度不变量
    int smax = 1 << km1;            // 残留串形态总数

    for (int l = 1; l <= n; l++)
        for (int r = 1; r <= n; r++)
            for (int s = 0; s < smax; s++) f[l][r][s] = NEG;
    for (int i = 1; i <= n; i++) f[i][i][a[i]] = 0;   // 单字符区间残留它自己,得分为 0

    for (int len = 2; len <= n; len++) {
        int rest = (len - 1) % km1;     // 该区间残留长度 = rest + 1
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (rest == 0) {
                // 残留 1 个字符:先拼满 k 位,再整体合并一次。
                // 后缀 [mid+1, r] 必须恰好收成 1 个字符,故 mid 以 k-1 为步长倒着取。
                ll best[2] = {NEG, NEG};
                for (int mid = r - 1; mid >= l; mid -= km1) {
                    for (int s = 0; s < smax; s++) {          // 前缀残留 k-1 位
                        ll base = f[l][mid][s];
                        if (base <= NEG / 2) continue;
                        for (int b = 0; b < 2; b++) {
                            ll tail = f[mid + 1][r][b];
                            if (tail <= NEG / 2) continue;
                            int id = (s << 1) | b;            // 拼出的 k 位串
                            ll val = base + tail + rule[id].score;
                            if (val > best[rule[id].ch]) best[rule[id].ch] = val;
                        }
                    }
                }
                f[l][r][0] = best[0];
                f[l][r][1] = best[1];
            } else {
                // 残留 rest + 1 个字符:前缀 [l, mid] 残留 rest 位,末尾再拼后缀的 1 个字符
                for (int mid = r - 1; mid >= l; mid -= km1) {
                    int lim = 1 << rest;
                    for (int s = 0; s < lim; s++) {
                        ll base = f[l][mid][s];
                        if (base <= NEG / 2) continue;
                        for (int b = 0; b < 2; b++) {
                            ll tail = f[mid + 1][r][b];
                            if (tail <= NEG / 2) continue;
                            int id = (s << 1) | b;
                            ll val = base + tail;
                            if (val > f[l][r][id]) f[l][r][id] = val;
                        }
                    }
                }
            }
        }
    }

    // w_i >= 1,合并只会加分,所以整串一定合并到最短,答案取残留串各形态的最大值
    ll ans = NEG;
    for (int s = 0; s < smax; s++) ans = max(ans, f[1][n][s]);
    printf("%lld\n", ans);
    return 0;
}

复杂度

  • 时间:状态数 O(n2)O(n^2),每个区间的分割点 O ⁣(nk−1)O\!\left(\frac{n}{k-1}\right) 个, 每个分割点枚举残留串形态 O(2k−1)O(2^{k-1}),故上界为 O ⁣(n3⋅2k−1k−1)O\!\left(\frac{n^3 \cdot 2^{k-1}}{k-1}\right)。 实际因为 rest\text{rest} 在 k−1k-1 个长度之间循环,平均的形态数是 2kk−1\frac{2^k}{k-1} 量级, n=300,k=8n = 300, k = 8 时约 5×1075 \times 10^7 次转移,C++ 实测远低于 1000 ms 限时。
  • 空间:ff 需要 O ⁣(n2⋅2k−1)O\!\left(n^2 \cdot 2^{k-1}\right) 个 64 位整数, 300×300×128≈1.2×107300 \times 300 \times 128 \approx 1.2 \times 10^7 个,约 93 MB,在 256 MB 限内。 Python 版只给每个区间开 2rest+12^{\text{rest}+1} 个槽位,总槽位不到 10510^5 个,内存不成问题。
  • 与 C++ 解法的关系:两份代码完全同构(同一转移、同一枚举顺序、同一哨兵语义), 差别只在存储:C++ 用定长三维全局数组换速度,Python 用 dict + 变长列表换内存。 Python 在 n=300,k=8n = 300, k = 8 的顶格点上会明显慢于 C++(同阶算法但常数大), 这是语言开销,不是算法降级。

总结

  • 先找不变量,再定状态:kk 个字符变 11 个,长度净减 k−1k-1,所以残留长度 (L−1) mod (k−1)+1(L-1) \bmod (k-1) + 1 与合并顺序无关。没有这一步,"区间合并后是什么"就无从刻画。
  • 小残留长度 = 可以状压:k⩽8k \leqslant 8 把残留串锁死在 77 位以内, 区间 DP 的第三维才敢开成 2k−12^{k-1},这是本题从指数搜索走向多项式算法的转折点。
  • 枚举分割点要顺着不变量跳:后缀必须收成 11 个字符,于是 midmid 以 k−1k-1 为步长 倒序取,比逐个枚举快 k−1k-1 倍,而且不会枚举到非法分割。
  • 拼满 kk 位就立刻合并:rest(L)=1\text{rest}(L) = 1 的分支与普通拼接分支只是"多查一次表、 多拿一次分",不需要额外的 DP 维度。
  • long long 不能省:wiw_i 最大 10910^9,n=300,k=2n = 300, k = 2 时最多合并 299299 次, 答案可达 3×10113 \times 10^{11},32 位整型必然溢出。
  • 本题随仓数据由同目录的 data.py 生成(用标准解现跑 .out),属于自造数据; 题面与 [HAOI2016] 字符合并(BZOJ 4565 / 洛谷 P3736)同源,为网络重建版本, 出题意图与官方原题可能存在偏差。