一、题目分析
本题给定两个长度为 n 的序列 a 和 b，要求构造一个长度为 n 的序列 c，其中 c_i 取值为 a_i 或者 b_i，目标是使得 \sum_{i = 2}^{n} |c_i - c_{i - 1}| 最小，并输出这个最小值。
二、解题思路
- 动态规划思路：
- 定义状态：我们使用二维数组
dp[i][j] 来表示在构造序列 c 的过程中，当处理到第 i 个位置，且 c_i 选择为 a_i（j = 0）或者 b_i（j = 1）时，前 i 个元素所构成的序列 c 的 \sum_{k = 2}^{i} |c_k - c_{k - 1}| 的最小值。
- 初始状态：
- 对于
dp[2][0]，表示 c_2 选择 a_2 时，c_1 有两种选择，即 a_1 或 b_1，所以 dp[2][0] = min(abs(a[2] - a[1]), abs(a[2] - b[1]))。
- 对于
dp[2][1]，表示 c_2 选择 b_2 时，c_1 同样有两种选择，即 dp[2][1] = min(abs(b[2] - a[1]), abs(b[2] - b[1]))。
- 状态转移方程：
- 当 c_i 选择 a_i（即
dp[i][0]）时，c_{i - 1} 可能选择了 a_{i - 1} 或者 b_{i - 1}。如果 c_{i - 1} 选择了 a_{i - 1}，那么当前的代价就是 abs(a[i] - a[i - 1]) 加上 dp[i - 1][0]；如果 c_{i - 1} 选择了 b_{i - 1}，那么当前的代价就是 abs(a[i] - b[i - 1]) 加上 dp[i - 1][1]。所以 dp[i][0] = min(abs(a[i] - a[i - 1]) + dp[i - 1][0], abs(a[i] - b[i - 1]) + dp[i - 1][1])。
- 同理，当 c_i 选择 b_i（即
dp[i][1]）时，dp[i][1] = min(abs(b[i] - a[i - 1]) + dp[i - 1][0], abs(b[i] - b[i - 1]) + dp[i - 1][1])。
- 最终答案：经过上述动态规划过程，
dp[n][0] 表示 c_n 选择 a_n 时的最小代价，dp[n][1] 表示 c_n 选择 b_n 时的最小代价，我们取两者中的较小值 min(dp[n][0], dp[n][1]) 作为最终答案。
三、代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e6 + 5;
int a[MAXN], b[MAXN], dp[MAXN][2];
int n;
signed main()
{
// 输入序列长度n
cin >> n;
// 输入序列a
for (int i = 1; i <= n; i++)
cin >> a[i];
// 输入序列b
for (int i = 1; i <= n; i++)
cin >> b[i];
// 初始化dp[2][0]
dp[2][0] = min(abs(a[2] - a[1]), abs(a[2] - b[1]));
// 初始化dp[2][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(abs(a[i] - a[i - 1]) + dp[i - 1][0], abs(a[i] - b[i - 1]) + dp[i - 1][1]);
dp[i][1] = min(abs(b[i] - a[i - 1]) + dp[i - 1][0], abs(b[i] - b[i - 1]) + dp[i - 1][1]);
}
// 输出最终答案
cout << min(dp[n][0], dp[n][1]);
return 0;
}
四、复杂度分析
- 时间复杂度：代码中有一个
for 循环，从 3 到 n 进行遍历，每次循环中进行常数次的操作，因此时间复杂度为 O(n)，其中 n 是序列的长度。
- 空间复杂度：使用了数组
a、b 和 dp，a 和 b 的长度为 n，dp 的大小为 n \times 2，所以空间复杂度为 O(n)。
---
完结撒花QWQ！
如果觉得文章有一些帮助的话不妨点个赞哦！谢谢！
健康查询