题解 AT4522 【Frog 1】
Chinshyo
2021-01-31 23:21:28
这道题是一道经典的线性动规。由于题目规则的设定，每次都是向前跳一格或两格，因此我们的状态转移方程就可以得出:
# AC CODE
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[100005], f[100005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];//无脑输入
f[1] = 0;//第一个不需要花费
f[2] = abs(a[2] - a[1]);//第二个直接由第一个跳来
for(int i = 3; i <= n; i++){
f[i] = min(f[i - 1] + abs(a[i - 1] - a[i]), f[i - 2] + abs(a[i - 2] - a[i]));//通过状态转移方程求解
}
cout << f[n] << endl;//输出解
return 0;
}
```