题解 AT4523 【Frog 2】

GZY007 · 2020-12-06 21:57:29 · 题解

线性DP简单题

• 令 dp[i]为当青蛙跳到石头i时使用的力气的最小值。
• 初始状态为 dp[1]=0,即去到第一块石头时花费为0。
• 动态转移方程：dp[i+k]=min(dp[i+k],dp[i]+|h[i+k]-h[i]|。
• 由于有k种跳的方法，用循环即可。

其他细节见代码，代码如下：

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int dp[200010],h[200010],m,k;
int main(){
    cin>>m>>k;
    memset(dp,2147483647,sizeof(dp));//初始化数组 
    for(int i=1;i<=m;i++) 
    {
        cin>>h[i];
    }
    dp[1]=0;//设置初始情况 
        for(int j=1;j<=m-1;j++)//向前递推 
        {
                for(int x=1;x<=k;x++)//枚举青蛙向前跳的情况 
                {
                    dp[j+x]=min(dp[j+x],dp[j]+abs(h[j]-h[j+x]));//更新答案 
                }
        }
    cout<<dp[m]; 
return 0;
}