C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題A (A – Frog 1) ～ 問題C (C – Vacation) を解いてみた.
■感想.
1. DPが良くわかってないので, 練習問題が用意されていることが有難いです.
※最近になって, 気付いた過去問でした.
■C++版プログラム(問題A／AC版).
|
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 26 27 28 29 30 31 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int N; cin >> N; LL H[N + 1]; H[0] = 0; for(int i = 1; i < N + 1; ++i) cin >> H[i]; // 2. DP更新. LL DP[N + 1]; for(int i = 0; i < N + 1; i++) DP[i] = 1e9; DP[0] = 0; DP[1] = 0; DP[2] = abs(H[2] - H[1]); for(int i = 3; i < N + 1; ++i){ // i - 2 から ジャンプしてきた. DP[i] = min(DP[i], DP[i - 2] + abs(H[i] - H [i - 2])); // i - 1 から ジャンプしてきた. DP[i] = min(DP[i], DP[i - 1] + abs(H[i] - H [i - 1])); } // 3. 出力. cout << DP[N] << endl; return 0; } |
■C++版プログラム(問題B／AC版).
|
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 26 27 28 29 30 31 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int N, K; cin >> N >> K; LL H[N + 1]; H[0] = 0; for(int i = 1; i < N + 1; ++i) cin >> H[i]; // 2. DP更新. LL DP[N + 1]; for(int i = 0; i < N + 1; i++) DP[i] = 1e9; DP[0] = 0; DP[1] = 0; DP[2] = abs(H[2] - H[1]); for(int i = 3; i < N + 1; ++i){ for(int k = 1; k <= K; k++){ // i - k から ジャンプしてきた. if(i - k > 0) DP[i] = min(DP[i], DP[i - k] + abs(H[i] - H [i - k])); } } // 3. 出力. cout << DP[N] << endl; return 0; } |
■C++版プログラム(問題C／AC版).
|
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 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int N; cin >> N; LL A[N + 1], B[N + 1], C[N + 1]; A[0] = B[0] = C[0] = 0; for(int i = 1; i < N + 1; ++i){ LL a, b, c; cin >> a >> b >> c; A[i] = a, B[i] = b, C[i] = c; } // 2. DP更新. LL DP[N + 1][3]; for(int i = 0; i < N + 1; i++) for(int j = 0; j < 3; j++) DP[i][j] = 0; // 配列DP について, 第二成分を, 活動A = 0, 活動B = 1, 活動C = 2 と見る. DP[1][0] = A[1], DP[1][1] = B[1], DP[1][2] = C[1]; for(int i = 2; i < N + 1; ++i){ // i日目 の活動 が A の 場合 -> (i - 1)日目は, 活動 B or C. DP[i][0] = max(DP[i - 1][1] + A[i], DP[i - 1][2] + A[i]); // i日目 の活動 が B の 場合 -> (i - 1)日目は, 活動 A or C. DP[i][1] = max(DP[i - 1][0] + B[i], DP[i - 1][2] + B[i]); // i日目 の活動 が C の 場合 -> (i - 1)日目は, 活動 A or B. DP[i][2] = max(DP[i - 1][0] + C[i], DP[i - 1][1] + C[i]); } // 3. 出力. LL ans = 0; for(int i = 0; i < 3; i++) ans = max(ans, DP[N][i]); cout << ans << endl; return 0; } |