B4163 [BCSP-X 2024 12 月初中组] 序列选择

https://www.luogu.com.cn/problem/B4163

题目描述

给定两个长度为 \( n \) 的序列 \( a, b \)，找出一个长为 \( n \) 的序列 \( c \)，满足对于 \( i = 1, 2, \cdots, n \)，有 \( c_i = a_i \) 或 \( c_i = b_i \)，使得 \(\sum_{i=2}^{n} |c_i - c_{i-1}|\) 最小，你只需要输出这个最小值。

输入格式

• 输入的第一行包含一个正整数 \( n \)。
• 接下来一行 \( n \) 个正整数，表示序列 \( a_i \)。
• 接下来一行 \( n \) 个正整数，表示序列 \( b_i \)。

输出格式

输出一行一个整数，表示 \(\sum_{i=2}^{n} |c_i - c_{i-1}|\) 的最小值。

输入输出样例 #1

输入 #1

5
1 3 4 2 5
2 5 4 2 1

输出 #1

5

说明/提示

样例 1 解释

令序列 \( c = [2, 3, 4, 2, 1] \)，此时 \(\sum_{i=2}^{n} |c_i - c_{i-1}| = 5\)，可以证明不存在更小的答案。

数据范围

• 对于 \(20\%\) 的数据，满足 \(n\leq 20\)。
• 对于 \(100\%\) 的数据，满足 \(1\leq n\leq 2\times 10^5\)，\(0\leq |a_i|,|b_i|\leq 10^9\)。