❀ 題目傳送門 ❀
https://atcoder.jp/contests/dp/tasks/dp_a
❀ 解題小技巧 ❀
基本上我用 Bottom-up 去推它，轉移式也不難想到，算是基礎題～
dp 為跳到第n個最省力之方法，我們只要比較從上一個跳到現在比較省力，還是從上上個比較省力即可。
❀ 參考程式碼 ❀
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| rock_num = int(input())
rocks = list(map(int, input().split()))
dp = [0 for i in range(rock_num)]
dp[1] = abs(rocks[1] - rocks[0])
for i in range(2, rock_num):
dp[i] = min(
dp[i-2] + abs(rocks[i]-rocks[i-2]),
dp[i-1] + abs(rocks[i]-rocks[i-1])
)
print(dp[rock_num - 1])
|
Cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
#define burst ios::sync_with_stdio(0); cin.tie(0);
int main(){
burst
int N;
cin >> N;
int stone[100005], dp[100005];
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= N; i++){
cin >> stone[i];
}
dp[1] = 0; dp[2] = abs(stone[1] - stone[2]);
for(int i = 3; i <= N; i++){
dp[i] = min(dp[i - 1] + abs(stone[i] - stone[i - 1]), dp[i - 2] + abs(stone[i] - stone[i - 2]));
}
cout << dp[N];
return 0;
}
|
❀ 心得幹話區 ❀
ㄟ對，好久沒用 python 寫了，差點就忘記我有點 python 的技能。
然而應該只有這題用 py ，因為心血來潮。
之後…說不定會更新 c++ 寫法（架構應該差不多也不用太期待）但真的有人在期待嗎
4/19 我真的更了，真神奇
