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

· · 题解

题目传送门

被拿捏了。

题目描述

直接给你两个长度为 n 的数组 a 和 b 构造一个数组 c，c_i 只能在 a_i 和 b_i 中选择一个赋值。赋值后，求出在 c 数组中相邻两数之差的绝对值之和的最小值。

思路

输入。

开一个 dp 数组，分为两种情况，一种表示当前值选择 a_i 的两种方案的最小值，一种表示当前值选择 b_i 的两种方案的最小值。注意，在找出最小值的时候一定要加上如果为该种方案对应的前一个数，这样才能找出完全的当前值。

输出最小值。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],b[200005],dp[3][200005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=2;i<=n;i++){
        dp[1][i]=min(abs(a[i]-a[i-1])+dp[1][i-1],abs(a[i]-b[i-1])+dp[2][i-1]);
        dp[2][i]=min(abs(b[i]-a[i-1])+dp[1][i-1],abs(b[i]-b[i-1])+dp[2][i-1]);
    }
    cout<<min(dp[1][n],dp[2][n]);
    return 0;
}

被拿捏现状

（给蒟蒻点个赞吧）