C++の練習を兼ねて, AtCoder Beginner Contest 052 の 問題D (D – Walk and Teleport) を解いてみた.
■感想.
1. 解答を見る前に, 正解に辿り着けたので, 及第点は取れたと思う.
2. 苦手な DP の 訓練になったと思う.
本家のサイトABC052/ARC067解説をご覧下さい.
■C++版プログラム(問題D/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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; LL X[210012]; LL dp[210012]; int main() { // 1. 入力情報取得. int N; LL A, B; scanf("%d %llu %llu", &N, &A, &B); for(int i = 0; i < N; i++) scanf("%llu", &X[i]); // 2. 疲労度の上昇値の合計の最小値を求める. for(int i = 1; i < N; i++){ dp[i] = dp[i - 1]; LL d = X[i] - X[i - 1]; dp[i] += min(A * d, B); } // 3. 出力 ~ 後処理. printf("%llu", dp[N - 1]); return 0; } |
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 |
[入力例] 4 2 5 1 2 5 7 [出力例] 11 ※AtCoderテストケースより [入力例] 7 1 100 40 43 45 105 108 115 124 [出力例] 84 ※AtCoderテストケースより [入力例] 7 1 2 24 35 40 68 72 99 103 [出力例] 12 ※AtCoderテストケースより [入力例] 12 2 55 1 3 5 33 55 81 123 212 220 303 321 333 [出力例] 400 |
■参照サイト
AtCoder Beginner Contest 052