题目描述
给定两个长度分别为 n 和 m 的整数序列 A=(a1,…,an) 与 B=(b1,…,bm)。你需要把这两个序列交错归并成一个长度为 n+m 的序列 C,规则如下:
- 归并过程中,每次只能从 A 或 B 的当前剩余前缀中取走一个元素,放到 C 的末尾;
- 从 A 取元素时保持 A 中原有相对顺序,从 B 取元素时保持 B 中原有相对顺序;
- 归并完成后,C 中所有来自 A 的元素依原序出现,所有来自 B 的元素依原序出现。
定义一次归并的代价为:
i=1∑n+m−1Ci−Ci+1
即相邻元素差的绝对值之和。
求所有合法归并方案中,代价的最小值。
例如,A=(1,4),B=(2,3)。一种合法归并为 C=(1,2,4,3),代价为 ∣1−2∣+∣2−4∣+∣4−3∣=1+2+1=4;另一种为 C=(1,2,3,4),代价为 1+1+1=3,这是最小值。
输入格式
第一行两个整数 n,m。
第二行 n 个整数 a1,…,an。
第三行 m 个整数 b1,…,bm。
输出格式
输出一���整数,表示最小代价。
样例
1 1
5
2
3
2 2
1 4
2 3
3
说明/提示
数据范围
- 对于 20% 的数据,n,m≤8;
- 对于 50% 的数据,n,m≤200;
- 对于 100% 的数据,1≤n,m≤3000,∣ai∣,∣bj∣≤109。
保证答案在 64 位有符号整数范围内。
提示
朴素的 O(nm(n+m)) 枚举归并顺序无法通过。注意归并状态只与“已经取走 A 的前 i 个、B 的前 j 个”以及“最后一个元素来自哪个序列”有关,可设计 O(nm) 的动态规划。
解析
解题思路
归并过程中,任意时刻的状态只取决于:已经从 A 取走了前 i 个、从 B 取走了前 j 个,以及最后一个放入 C 的元素来自哪个序列。因为代价只与相邻元素有关,我们只需知道最后一个元素是谁,就能计算下一个元素的贡献。
设:
- dpA[i][j]:取完 A 前 i 个、B 前 j 个,且最后一个元素是 ai 时的最小代价;
- dpB[i][j]:同理,最后一个元素是 bj。
转移:
- 若最后取 ai,前一个元素可能是 ai−1 或 bj:$$dpA[i][j]=\min\big(dpA[i-1][j]+|a_i-a_{i-1}|,\ dpB[i-1][j]+|a_i-b_j|\big)$$
- 若最后取 bj,前一个元素可能是 ai 或 bj−1:$$dpB[i][j]=\min\big(dpA[i][j-1]+|b_j-a_i|,\ dpB[i][j-1]+|b_j-b_{j-1}|\big)$$
边界:dpA[0][0]=dpB[0][0]=0,其余初值为无穷大。注意 i=0 时只能连续取 B,j=0 时只能连续取 A。
答案:min(dpA[n][m],dpB[n][m])。
算法选择理由
朴素枚举所有归并顺序是指数级的。观察到状态只与两个前缀长度和最后一个来源有关,具有最优子结构,因此使用动态规划。状态数 O(nm),每个状态 O(1) 转移。
复杂度分析
- 时间复杂度:O(nm),最大 3000×3000=9×106,可在 1 秒内通过。
- 空间复杂度:使用滚动数组,O(m);若开二维数组则 O(nm)。
注意答案可能超过 32 位,需使用 long long,无穷大取足够大的常数(如 LLONG_MAX/4)避免溢出。
来源
AI 生成 · 云端大模型(域):deepseek-chat · NOI/NOI+/CTS · 动态规划