简单·题解

$\color{red}不开long long见祖宗$

我去，这么简单！

很经典的线性 DP 入门题。

设 dp[i] 表示跳到第 i 块石阶的最小体力消耗。

因为青蛙每次只能从 i-1 或 i-2 跳过来，所以：

从 i-1 跳过来：dp[i-1] + abs(h[i] - h[i-1])

从 i-2 跳过来：dp[i-2] + abs(h[i] - h[i-2])

两者取较小值即可。

边界：dp[1] = 0（起点不用消耗体力）。

最后答案就是 dp[n]。

题解来源于JTBG

#include <bits/stdc++.h>

#ifdef USE_JTBG_H
	#undef JTBG_ALL
	#undef _agree_
	#define JTBG_ALL
	#undef _agree_
	#include "jtbg.h"
#endif

using namespace std;
long long n, h[100010], dp[100010];
int main()
{
	cin >> n;
	for (int i = 2; i <= n + 1; i++)
	{
		cin >> h[i];
	}
	for (int i = 3; i <= n + 1; i++)
	{
		dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] +  abs(h[i - 2] - h[i]));
	}
	cout << dp[n+1]  << endl;
	return 0;
}