题目描述

给定两个长度为 n 的序列 a,b，找出一个长为 n 的序列 c，满足对于 i=1,2,⋯,n，有 ci​=ai​ 或 ci​=bi​，使得 ∑i=2n​∣ci​−ci−1​∣ 最小，你只需要输出这个最小值。

输入格式

• 输入的第一行包含一个正整数 n。
• 接下来一行 n 个整数，表示序列 ai​。
• 接下来一行 n 个整数，表示序列 bi​。

输出格式

输出一行一个整数，表示 ∑i=2n​∣ci​−ci−1​∣ 的最小值。

输入输出样例

输入 #1复制

5
1 3 4 2 5
2 5 4 2 1

输出 #1复制

5

数据范围

• 对于 20% 的数据，满足 n≤20。
• 对于 100% 的数据，满足 1≤n≤2×105，0≤∣ai​∣,∣bi​∣≤109。

附件下载

seq.zip50.62KB

总体就是按照题目要求，求出最小值

第一种20分的写法就是DFS纯暴力

满分写法用DP来写

就是继承之前以a[i - 1]和b[i - 1]结尾的最佳情况

相当于

a1[i] = min(a1[i - 1] + abs(a[i - 1] - a[i]),b1[i - 1] + abs(b[i - 1] - a[i]));

和

b1[i] = min(a1[i - 1] + abs(a[i - 1] - b[i]),b1[i - 1] + abs(b[i - 1] - b[i]));

仔细想想就知道了

代码也就很好写了

以下是代码

#include <bits/stdc++.h>
using namespace std;
int n;
long long a[200100] = {0},b[200100] = {0},a1[200100] = {0},b1[200100] = {0};
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++){
		a1[i] = min(a1[i - 1] + abs(a[i - 1] - a[i]),b1[i - 1] + abs(b[i - 1] - a[i]));
		b1[i] = min(a1[i - 1] + abs(a[i - 1] - b[i]),b1[i - 1] + abs(b[i - 1] - b[i]));
	}
	cout<<min(a1[n],b1[n])<<endl;
	return 0;
}

点个赞吧求求了

想要粉丝