AT4522 题解

乐乐乐还在乐 · 2021-08-10 16:41:50 · 题解

AT4522 题解

题目传送门

题目大意

一只青蛙要从 1 号石头跳到 n 号石头上。

每次跳跃需消耗一些费用。

求青蛙跳到 n 号石头需要的最小总费用。

分析题目

这道题明显就是一道动态规划。

康康数据范围：2 \le N \le 10^5, O(n) 能过。

前置工作

我们先定义一个函数 cost(i,j),用来计算从第 i 块石头跳到第 j 块石头的花费。

由题意，cost(i,j)=|a_i-a_j|。

思考算法

dp 三件套：状态、状态转移方程、初始状态。

状态：

用 dp_i 表示跳到第i块石头所需的最小费用。

状态转移方程：

即:跳到第 i 块石头所需的最小费用 = 前两块的最小费用 + 跳过来的消耗。

初始状态：

跳到第一块石头无需消耗(跳都不用跳)，

跳到第二块石头需消耗 cost(1,2)。

即 dp(1)=0,dp(2)=cost(1,2)。

接着就可以愉快地dp啦。

for(int i=3;i<=n;i++)
    dp[i]=min(dp[i-1]+cost(i,i-1),dp[i-2]+cost(i,i-2));

附上AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e5+5;

int n;
int h[MAXN]={0};
int dp[MAXN]={0};//dp[i]表示跳到第i块石头所需的最小费用

int cost(int i,int j){//cost函数表示从第i块石头跳到第j块石头的花费
    return abs(h[i]-h[j]);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);

    dp[2]=cost(1,2);//初始化，2号石头只能从前一块（1号）石头跳来
    //注：不用初始化dp[1]（它本来就是0）

    for(int i=3;i<=n;i++)
        dp[i]=min(dp[i-1]+cost(i,i-1),dp[i-2]+cost(i,i-2));

    printf("%d",dp[n]);
    return 0;
}