Educational DP Contest A
こちらの記事を参考にしつつ練習。
もらうDP
#include<iostream>
using namespace std;
int main() {
// 入力を受け取る
int n;
cin >> n;
int h[n], dp[n];
for (int i=0; i<n; i++) cin >> h[i];
// 最初2つを記録
dp[0] = 0;
dp[1] = abs(h[1] - h[0]);
// 最初2つをもとに、前の2つから情報をもらってdpを記録していく
for (int i=2; i<n; i++) {
dp[i] = min(
dp[i-2] + abs(h[i-2] - h[i]),
dp[i-1] + abs(h[i-1] - h[i])
);
}
cout << dp[n-1] << endl;
}
配るDP
#include<iostream>
using namespace std;
const int INF = 1 << 30
int main() {
// 入力を受け取る
int n;
cin >> n;
int h[n], dp[n];
for (int i=0; i<n; i++) {
cin >> h[i];
dp[i] = INF;
}
// 最初1つを記録
dp[0] = 0;
// 最初1つをもとに、後ろ2つのdpを記録していく
for (int i = 0; i < n; i++) {
dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1]- h[i]));
dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2]- h[i]));
}
cout << dp[n-1] << endl;
}
メモ化再帰
#include<iostream>
#include<cmath>
using namespace std;
const int INF = 1 << 30;
int h[100000];
int dp[100000];
// i番目の足場に行くまでの最小コストを返す関数
int rec(int i) {
// メモされていたらメモされた値を返す
if (dp[i] < INF) return dp[i];
// i = 0 なら明示的に値を返す
if (i == 0) return 0;
// 再帰的にrecを呼び出す
int ret = min(
rec(i-1) + abs(h[i] - h[i-1]),
i != 1 ? rec(i-2) + abs(h[i] - h[i-2]) : INF
);
// 結果をメモする
dp[i] = ret;
return ret;
}
int main() {
// 入力を受け取る
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> h[i];
// メモを初期化する
dp[i] = INF;
}
cout << rec(n-1) << endl;
}
