利用区间合并后残留长度恒为 (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
形式化题目
给定长度为
求任意次(含
注意题目不要求把整串合并到某个固定长度:可以随时停手,但
正解
思路
朴素做法。 直接搜索:每一步枚举当前串里相邻的
瓶颈在哪? 换成区间 DP 也躲不开同一个问题:只记"区间
关键观察一:残留长度是不变量。 每次合并把
| 区间长度 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 残留长度( |
1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
| 残留长度( |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 1 | 2 | 3 |
读表要点:残留长度只由
关键观察二:分割点只需以
关键观察三:拼满
状态与转移。 设
- 初始化:
,其余全部 。 - 转移(按
递增):
- 答案:
。
正确性。 对任意合并方案,最终残留串从左到右的每个字符都对应原来位置的一段连续区间,
这些区间首尾相接铺满
样例推演。 样例 1 0 1,规则表为
— 表示
| 区间 |
长度 |
残留长度 | 说明 | ||
|---|---|---|---|---|---|
| 1 | 1 | — | 0 | 基态,残留串 1 |
|
| 1 | 1 | 0 | — | 基态,残留串 0 |
|
| 1 | 1 | — | 0 | 基态,残留串 1 |
|
| 2 | 1 | 20 | — | 合并 10 |
|
| 2 | 1 | — | 10 | 合并 01 |
|
| 3 | 1 | — | 40 | 走 |
最后一行是关键:10)只得到 01)得到
代码
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 的稀疏表):
/**
* 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;
}复杂度
- 时间:状态数
,每个区间的分割点 个, 每个分割点枚举残留串形态 ,故上界为 。 实际因为 在 个长度之间循环,平均的形态数是 量级, 时约 次转移,C++ 实测远低于 1000 ms 限时。 - 空间:
需要 个 64 位整数, 个,约 93 MB,在 256 MB 限内。 Python 版只给每个区间开 个槽位,总槽位不到 个,内存不成问题。 - 与 C++ 解法的关系:两份代码完全同构(同一转移、同一枚举顺序、同一哨兵语义),
差别只在存储:C++ 用定长三维全局数组换速度,Python 用
dict+ 变长列表换内存。 Python 在的顶格点上会明显慢于 C++(同阶算法但常数大), 这是语言开销,不是算法降级。
总结
- 先找不变量,再定状态:
个字符变 个,长度净减 ,所以残留长度 与合并顺序无关。没有这一步,"区间合并后是什么"就无从刻画。 - 小残留长度 = 可以状压:
把残留串锁死在 位以内, 区间 DP 的第三维才敢开成 ,这是本题从指数搜索走向多项式算法的转折点。 - 枚举分割点要顺着不变量跳:后缀必须收成
个字符,于是 以 为步长 倒序取,比逐个枚举快 倍,而且不会枚举到非法分割。 - 拼满
位就立刻合并: 的分支与普通拼接分支只是"多查一次表、 多拿一次分",不需要额外的 DP 维度。 long long不能省:最大 , 时最多合并 次, 答案可达 ,32 位整型必然溢出。 - 本题随仓数据由同目录的
data.py生成(用标准解现跑.out),属于自造数据; 题面与[HAOI2016]字符合并(BZOJ 4565 / 洛谷 P3736)同源,为网络重建版本, 出题意图与官方原题可能存在偏差。