[普及-]93766题解

吐槽

怎么管的这么怂，3个人代码里（除了我）2个AI，1个复制别人的AI代码。

题目大意

给你n块石头，每次跳跃跳下一个或者空一格，跳一次的代价是 $\text{abs}(a_i - a_j)$ 其中 $i,j$ 分别指起点位置和重点位置。要求你求出跳到第 $n$ 块石头的最小代价。

思路

本题考虑dp。

设 $dp_i$ 为跳到第 $i$ 块石头的最小值。同时我们发现，想到达第 $i$ 石头，必须从 $i - 1$ 或 $i - 2$到达。因此 $dp_i$ 的值也一定只由 $dp_{i - 1} , dp_{i - 2}$ 决定。很快我们就能发现转移方程：

$$dp_i = \min(dp_{i - 1} + \text{abs}(a_i - a_{i - 1}) , dp_{i - 2} + \text{abs}(a_i - a_{i - 2}))$$

最后输出 $dp_n$即可。

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

当然可以使用滚动数组（不给代码自己写）。