#3731. 双序列分段归并代价

双序列分段归并代价

题目描述

给定两个长度分别为 nn 和 mm 的整数序列 A=(a1,…,an)A=(a_1,\dots,a_n) 与 B=(b1,…,bm)B=(b_1,\dots,b_m)。你需要把这两个序列交错归并成一个长度为 n+mn+m 的序列 CC,规则如下:

  • 归并过程中,每次只能从 AA 或 BB 的当前剩余前缀中取走一个元素,放到 CC 的末尾;
  • 从 AA 取元素时保持 AA 中原有相对顺序,从 BB 取元素时保持 BB 中原有相对顺序;
  • 归并完成后,CC 中所有来自 AA 的元素依原序出现,所有来自 BB 的元素依原序出现。

定义一次归并的代价为:

∑i=1n+m−1∣Ci−Ci+1∣\sum_{i=1}^{n+m-1} \big|C_i-C_{i+1}\big|

即相邻元素差的绝对值之和。

求所有合法归并方案中,代价的最小值。


例如,A=(1,4)A=(1,4),B=(2,3)B=(2,3)。一种合法归并为 C=(1,2,4,3)C=(1,2,4,3),代价为 ∣1−2∣+∣2−4∣+∣4−3∣=1+2+1=4|1-2|+|2-4|+|4-3|=1+2+1=4;另一种为 C=(1,2,3,4)C=(1,2,3,4),代价为 1+1+1=31+1+1=3,这是最小值。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数 a1,…,ana_1,\dots,a_n。

第三行 mm 个整数 b1,…,bmb_1,\dots,b_m。

输出格式

输出一���整数,表示最小代价。

样例

1 1
5
2 
3 
2 2
1 4
2 3 
3 

说明/提示

数据范围

  • 对于 20%20\% 的数据,n,m≤8n,m\le 8;
  • 对于 50%50\% 的数据,n,m≤200n,m\le 200;
  • 对于 100%100\% 的数据,1≤n,m≤30001\le n,m\le 3000,∣ai∣,∣bj∣≤109|a_i|,|b_j|\le 10^9。

保证答案在 6464 位有符号整数范围内。

提示

朴素的 O(nm(n+m))O(nm(n+m)) 枚举归并顺序无法通过。注意归并状态只与“已经取走 AA 的前 ii 个、BB 的前 jj 个”以及“最后一个元素来自哪个序列”有关,可设计 O(nm)O(nm) 的动态规划。

解析

解题思路

归并过程中,任意时刻的状态只取决于:已经从 AA 取走了前 ii 个、从 BB 取走了前 jj 个,以及最后一个放入 CC 的元素来自哪个序列。因为代价只与相邻元素有关,我们只需知道最后一个元素是谁,就能计算下一个元素的贡献。

设:

  • dpA[i][j]dpA[i][j]:取完 AA 前 ii 个、BB 前 jj 个,且最后一个元素是 aia_i 时的最小代价;
  • dpB[i][j]dpB[i][j]:同理,最后一个元素是 bjb_j。

转移:

  • 若最后取 aia_i,前一个元素可能是 ai−1a_{i-1} 或 bjb_j:$$dpA[i][j]=\min\big(dpA[i-1][j]+|a_i-a_{i-1}|,\ dpB[i-1][j]+|a_i-b_j|\big)$$
  • 若最后取 bjb_j,前一个元素可能是 aia_i 或 bj−1b_{j-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]=0dpA[0][0]=dpB[0][0]=0,其余初值为无穷大。注意 i=0i=0 时只能连续取 BB,j=0j=0 时只能连续取 AA。

答案:min⁡(dpA[n][m],dpB[n][m])\min(dpA[n][m],dpB[n][m])。

算法选择理由

朴素枚举所有归并顺序是指数级的。观察到状态只与两个前缀长度和最后一个来源有关,具有最优子结构,因此使用动态规划。状态数 O(nm)O(nm),每个状态 O(1)O(1) 转移。

复杂度分析

  • 时间复杂度:O(nm)O(nm),最大 3000×3000=9×1063000\times3000=9\times10^6,可在 1 秒内通过。
  • 空间复杂度:使用滚动数组,O(m)O(m);若开二维数组则 O(nm)O(nm)。

注意答案可能超过 3232 位,需使用 long long,无穷大取足够大的常数(如 LLONG_MAX/4)避免溢出。

来源

AI 生成 · 云端大模型(域):deepseek-chat · NOI/NOI+/CTS · 动态规划