Atcoder DP Contest pB

Atcoder DP Contest pB

題敘

https://atcoder.jp/contests/dp/tasks/dp_b

對於每個點 $i$ 可以從點 $i-1, i-2, … , i-k$ 轉移
而轉移的花費為 $\mid arr[i]-arr[i-k] \mid$
求到點 $n$ 的最小花費

想法

對於每種轉移方式求最大值
定義 $DP[i]$ 表示點 $i$ 的最小花費
則有轉移式 $DP[i] = min(DP[i], DP[i-k] + \mid arr[i]-arr[i-k] \mid)$
且 $DP[0] = 0, DP[1]=abs(arr[0]-arr[1])$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//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,k,arr[MaxN],dp[MaxN];
int main(){
IOS
while(cin>>n>>k){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
dp[i]=INT_MAX;
}
dp[0]=0;
for(int i=1 ; i<n ; i++){
for(int j=1 ; i-j>=0 && j<=k ; j++){
dp[i]=min(dp[i], dp[i-j] + abs(arr[i]-arr[i-j]));
}
}
cout<<dp[n-1]<<'\n';
}
return 0;
}

複雜度

有 $n$ 種狀態,每種狀態轉移複雜度為 $O(k)$
總複雜度 $O(nk)$