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

bh2013 · 2025-02-23 11:50:34 · 题解

题目传送门

题目分析:

本题的目标是从两个长度为 n 的序列 a 和 b 中构造出一个长度为 n 的序列 c，对于每个位置 i，c[i] 可以选择等于 a[i] 或者 b[i]，我们需要使得 c 序列中相邻元素差值的绝对值之和最小，最后输出这个最小值。

解题思路:

我们可以使用动态规划的方法来解决这个问题。定义两个状态数组 dp1 和 dp2，其中：

·dp1[i] 表示当 c[i] 选择 a[i] 时，前 i 个元素满足条件的最小相邻元素差值绝对值之和。

·dp2[i] 表示当 c[i] 选择 b[i] 时，前 i 个元素满足条件的最小相邻元素差值绝对值之和。

状态转移方程如下：

·当 c[i] 选择 a[i] 时，c[i-1] 可以选择 a[i-1] 或者 b[i-1]，我们取这两种情况下的最小值加上 |a[i] - a[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] 选择 b[i] 时，同理可得 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])。

代码：

#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-1，每次循环内的操作时间复杂度为 O(1)，因此总的时间复杂度为 O(n)。

·空间复杂度：使用了两个长度为 n 的数组 dp1 和 dp2 来保存中间结果，因此空间复杂度为 O(n)。

注意事项:

·输入的序列长度为 n，数组下标从 0 开始，因此最终结果需要取 dp1[n-1] 和 dp2[n-1] 中的最小值。

·代码中使用了 abs 函数来计算绝对值，确保差值为非负数。

谢谢大家观看我的题解