DPまとめコンテスト A - Frog 1
概要
数列がある。この数列を0つとばし、1つとばしのどちらかで進む。
からに進むとき、コストがかかる。
からに進むときのコストの総和の最小値を求めよ。
制約
方針
コストを配列にする。
まで進むときの最小コストをとすると、は下記の通り遷移する。
解答
Submission #3938370 - Educational DP Contest / DP まとめコンテスト
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define rep(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--) #define rrep(i,n) RFOR(i,n,0) using namespace std; typedef long long ll; typedef unsigned long long ull; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; ll h[n]; rep(i, n) cin >> h[i]; ll c[n]; c[0] = 0; c[1] = abs(h[1] - h[0]); for(int i = 1; i+1 <= n-1; i++){ c[i+1] = min(c[i-1] + abs(h[i+1] - h[i-1]), c[i] + abs(h[i+1] - h[i])); } cout << c[n-1] << endl; }