生命不息,奋斗不止

题解 AT4522 【Frog 1】

2021-01-31 23:21:28


这道题是一道经典的线性动规。由于题目规则的设定,每次都是向前跳一格或两格,因此我们的状态转移方程就可以得出:

AC CODE

#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;
}