专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipxpor2
此快照首次捕获于
2025/12/03 19:39
3 个月前
此快照最后确认于
2025/12/03 19:39
3 个月前
查看原文

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

还是我的一个朋友 @Leo926 告诉了我这道题又水又可以写题解，我就快快过来发一篇。

1. 解题思路

一眼动态规划水题。直接来说定义：fi,jf_{i,j} 表示 cc 序列中第 ii 位为 aia_i (j=0)(j=0) 或 bib_i (j=1)(j = 1) 时最小的答案。最终答案就是 min⁡{fn,0,fn,1}\min\{f_{n,0}, f_{n,1}\}。
现在我们来分析转移方程：
fi,0=min⁡{fi−1,0+∣ai−ai−1∣,fi−1,1+∣ai−bi−1∣}fi,1=min⁡{fi−1,0+∣bi−ai−1∣,fi−1,1+∣bi−bi−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}|\}
最后来确定初始条件：f1,0=f1,1=0f_{1,0} = f_{1,1} = 0。

2. 代码实现

O(n)O(n) 时间复杂度秒掉。
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;
}

评论

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

正在加载评论...