[題解]TIOJ 1019 Jumping Up

tioj-1019 Jumping Up

題序

定義

定義 dp[i] 為第 0 個到第 i 個鈴鐺的最小移動水平距離總和

轉移方式

令$a0,a_1…a{n-1}$為相對於螢幕正中央的水平位移，選擇跳一格或跳兩格。

$dp[i] = min(dp[i-1]+abs(ai-a{i-1}),dp[i-2]+abs(ai-a{i-2}))$

邊界條件

$dp[0] = 0,$ $dp[1] = abs(a_1-a_0)$

程式碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,N;

signed main(){
    cin>>T;
    while(T--){
        cin>>N;
        int arr[N+1],dp[N+1];
        memset(arr, 0, sizeof(arr));
        memset(dp, 0, sizeof(dp));
        
        for(int i=0;i<N;i++)cin>>arr[i];
        dp[0] = 0;dp[1] = abs(arr[1]-arr[0]);
        
        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]<<endl;
    }
}

複雜度

這一題$dp_i$只會跟前兩項有關係，好像可以用滾動DP來優化空間，可以以後嘗試看看！