Try   HackMD

演算法題 - A Frog 1 - Atcoder - by PeterWang

題目資訊 Atcoder DP contest

tags: Atcoder DP

題目敘述

N 個石頭,給個石頭有不同高度,一隻青蛙從第一顆石頭開始,每次可以選擇跳一格或兩格而每從第 i 個跳到第 j 個的花費為兩石頭高度相減的絕對值,最後回傳總花費最小值為何。

輸入:

先輸入總共有 N 個石頭,再依序輸入第 i 個石頭的高度

輸出:

到達地 N 個石頭前最小的花費

解題思路

每到一塊石頭,就去比較前兩塊跳過來的花費,並選擇最小值加總。

程式碼

#include <iostream> #include <cmath> using namespace std; int main() { int n; cin>>n; int a[n]; int dp[n]; for(int i=0;i<n;i++){ cin>>a[i]; } dp[0]=0; dp[1]=abs(a[1]-a[0]); for(int i=2;i<n;i++){ dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2])); } cout<<dp[n-1]<<endl; return 0; }

資料來源

Atcoder
題目敘述

備註

PeterWang
Sun, Jun 13, 2021 10:00 AM