Koios1143的筆記

Atcoder DP Contest pA

發表於 分類於

Atcoder DP Contest pA

題敘

https://atcoder.jp/contests/dp/tasks/dp_a
跳到第 $i$ 格的方法有兩種

  • 從 $i-1$ 格跳，花費 $\mid arr[i]-arr[i-1] \mid$
  • 從 $i-2$ 格跳，花費 $\mid arr[i]-arr[i-2] \mid$

求跳到第 $n$ 格的最小花費

想法

對於每個格子 $i$ 只能從 $i-1$ 和 $i-2$ 轉移過來，因此只需要判斷從誰走過來最小就能保證會是最佳解
定義 $DP[i]$ 表示第 $i$ 格的最小花費
則有轉移式 $DP[i] = min(DP[i-1] + \mid arr[i]-arr[i-1] \mid,\ DP[i-2] + \mid arr[i]-arr[i-2] \mid)$
且 $DP[0] = 0, DP[1] = abs(arr[1]-arr[0])$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
const int MaxN = 100005;
int n,arr[MaxN],dp[MaxN];
int main(){
	IOS
	while(cin>>n){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		dp[0]=0;
		dp[1]=abs(arr[0]-arr[1]);
		for(int i=2 ; i<n ; i++){
			dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i]-arr[i-2]));
		}
		cout<<dp[n-1]<<"\n";
	}
	return 0;
}

複雜度

有 $n$ 種狀態，每種狀態的轉移複雜度為 $O(1)$
總複雜度 $O(n)$