专栏文章

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

bbh2013
B4163题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq67ipb
此快照首次捕获于
2025/12/03 23:37
3 个月前
此快照最后确认于
2025/12/03 23:37
3 个月前
查看原文
题目传送门
题目分析:
本题的目标是从两个长度为 nn 的序列 aa 和 bb 中构造出一个长度为 nn 的序列 cc，对于每个位置 ii，c[i]c[i] 可以选择等于 a[i]a[i] 或者 b[i]b[i]，我们需要使得 cc 序列中相邻元素差值的绝对值之和最小，最后输出这个最小值。
解题思路:
我们可以使用动态规划的方法来解决这个问题。定义两个状态数组 dp1dp1 和 dp2dp2，其中：
·dp1[i]dp1[i] 表示当 c[i]c[i] 选择 a[i]a[i] 时，前 ii 个元素满足条件的最小相邻元素差值绝对值之和。
·dp2[i]dp2[i] 表示当 c[i]c[i] 选择 b[i]b[i] 时，前 ii 个元素满足条件的最小相邻元素差值绝对值之和。
状态转移方程如下：
·当 c[i]c[i] 选择 a[i]a[i] 时，c[i−1]c[i-1] 可以选择 a[i−1]a[i-1] 或者 b[i−1]b[i-1]，我们取这两种情况下的最小值加上 ∣a[i]−a[i−1]∣|a[i] - a[i-1]| 或 ∣a[i]−b[i−1]∣|a[i] - b[i-1]|，即 dp1[i]=min⁡(dp1[i−1]+∣a[i]−a[i−1]∣,dp2[i−1]+∣a[i]−b[i−1]∣)dp1[i] = \min(dp1[i-1] + |a[i] - a[i-1]|, dp2[i-1] + |a[i] - b[i-1]|)。
·当 c[i]c[i] 选择 b[i]b[i] 时，同理可得 dp2[i]=min⁡(dp1[i−1]+∣b[i]−a[i−1]∣,dp2[i−1]+∣b[i]−b[i−1]∣)dp2[i] = \min(dp1[i-1] + |b[i] - a[i-1]|, dp2[i-1] + |b[i] - b[i-1]|)。 最终的答案就是 min⁡(dp1[n−1],dp2[n−1])\min(dp1[n-1], dp2[n-1])。
代码：
C
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[200005], b[200005], dp[200005][2];

signed main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) cin >> b[i];
	dp[2][0] = min(abs(a[2] - a[1]), abs(a[2] - b[1]));
	dp[2][1] = min(abs(b[2] - a[1]), abs(b[2] - b[1]));
	for (int i = 3; i <= n; i ++) {
		dp[i][0] = min(dp[i - 1][0] + abs(a[i] - a[i - 1]), dp[i - 1][1] + abs(a[i] - b[i - 1]));
		dp[i][1] = min(dp[i - 1][0] + abs(b[i] - a[i - 1]), dp[i - 1][1] + abs(b[i] - b[i - 1]));
	}
	cout << min(dp[n][0], dp[n][1]) << endl;
	return 0;
}
复杂度分析:
·时间复杂度：代码中主要的操作是一个循环，循环次数为 n−1n-1，每次循环内的操作时间复杂度为 O(1)O(1)，因此总的时间复杂度为 O(n)O(n)。
·空间复杂度：使用了两个长度为 nn 的数组 dp1dp1 和 dp2dp2 来保存中间结果，因此空间复杂度为 O(n)O(n)。
注意事项:
·输入的序列长度为 nn，数组下标从 00 开始，因此最终结果需要取 dp1[n−1]dp1[n-1] 和 dp2[n−1]dp2[n-1] 中的最小值。
·代码中使用了 absabs 函数来计算绝对值，确保差值为非负数。
谢谢大家观看我的题解

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...