自动搬运

查看原文

来自洛谷，原作者为

	oVo_yangxy ⸸ ​"Mergi In Profundis."|The Lord.G ⸸​

搬运于2025-08-24 21:17:29，当前版本为作者最后更新于2025-03-19 15:48:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

被拿捏了。

题目描述

直接给你两个长度为 $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;
}

被拿捏现状

（给蒟蒻点个赞吧）