C++の練習を兼ねて, AtCoder Beginner Contest 175 の 問題E (Picking Goods) を解いてみた.
■感想.
1. dp更新式を首尾よく構築できたので, AC版に到達できたと思う.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 175 解説をご覧下さい.
■C++版プログラム(問題E/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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back LL dp[3030][3030][4]; // 第一成分: 行, 第二成分: 列, 第三成分: 同じ行で, 拾ったアイテム個数. LL board[3030][3030]; int main(){ // 1. 入力情報. int R, C, K; scanf("%d %d %d", &R, &C, &K); rep(i, K){ int r, c; LL v; scanf("%d %d %lld", &r, &c, &v); r--, c--; board[r][c] = v; } // 2. dp更新. rep(r, R + 1){ rep(c, C + 1){ // 次行に進む場合. if(r < R){ LL rMax = 0; // 移動前の行で, アイテムが置いてあった場合を考慮. rep(k, 4) rMax = max(rMax, dp[r][c][k] + board[r][c] * (k < 3)); rep(k, 4) dp[r + 1][c][k] = max(dp[r + 1][c][k], rMax); } // 次列に進む場合. if(c < C){ rep(k, 4) dp[r][c + 1][k] = max(dp[r][c + 1][k], dp[r][c][k]); // アイテムが置いてあった場合. LL v = board[r][c]; if(v) rep(k, 3) dp[r][c + 1][k + 1] = max(dp[r][c + 1][k + 1], dp[r][c][k] + v); } } } // 3. 出力. LL ans = 0; rep(k, 4) ans = max(ans, dp[R][C][k]); printf("%lld\n", ans); 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
[入力例] 2 2 3 1 1 3 2 1 4 1 2 5 [出力例] 8 ※AtCoderテストケースより [入力例] 2 5 5 1 1 3 2 4 20 1 2 1 1 3 4 1 4 2 [出力例] 29 ※AtCoderテストケースより [入力例] 4 5 10 2 5 12 1 5 12 2 3 15 1 2 20 1 1 28 2 4 26 3 2 27 4 5 21 3 5 10 1 3 10 [出力例] 142 ※AtCoderテストケースより [入力例] 11 7 33 1 1 1 1 3 3 1 5 13 1 6 5 1 7 7 2 2 2 2 7 8 3 3 3 3 5 7 4 2 3 4 4 4 4 7 11 5 5 5 6 3 8 6 6 6 7 1 20 7 4 19 7 6 18 7 7 7 8 1 9 8 2 17 8 4 23 8 5 27 8 6 11 9 2 10 9 4 12 9 5 19 9 7 15 10 3 17 11 2 33 11 4 12 11 5 25 11 7 5 [出力例] 139 |
■参照サイト
AtCoder Beginner Contest 175