题解：B4163 [BCSP-X 2024 12 月初中组] 序列选择
superLouis
·
·
题解
题解：B4163 [BCSP-X 2024 12 月初中组] 序列选择
还是我的一个朋友 @Leo926 告诉了我这道题又水又可以写题解，我就快快过来发一篇。
1. 解题思路
一眼动态规划水题。直接来说定义：f_{i,j} 表示 c 序列中第 i 位为 a_i (j=0) 或 b_i (j = 1) 时最小的答案。最终答案就是 \min\{f_{n,0}, f_{n,1}\}。
现在我们来分析转移方程：
f_{i,0} = \min\{f_{i-1,0} + |a_i - a_{i-1}|, f_{i-1,1} + |a_i - b_{i-1}|\}\\f_{i,1} = \min\{f_{i-1,0} + |b_i - a_{i-1}|, f_{i-1,1} + |b_i - b_{i-1}|\}
最后来确定初始条件：f_{1,0} = f_{1,1} = 0。
2. 代码实现
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 2e5 + 10;
int n, a[maxn], b[maxn], f[maxn][2];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
f[1][0] = f[1][1] = 0;
for (int i = 2; i <= n; i++) {
f[i][0] = min(f[i - 1][0] + abs(a[i] - a[i - 1]), f[i - 1][1] + abs(a[i] - b[i - 1]));
f[i][1] = min(f[i - 1][0] + abs(b[i] - a[i - 1]), f[i - 1][1] + abs(b[i] - b[i - 1]));
}
cout << min(f[n][0], f[n][1]) << "\n";
return 0;
}
```