C++の練習を兼ねて, AtCoder Beginner Contest 145 の 問題E (All-you-can-eat) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 145 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc145/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; #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 a first #define b second #define all(x) x.begin(), x.end() int dp[3030][3030]; int main(){ // 1. 入力情報. int N, T; scanf("%d %d", &N, &T); vp v(N); rep(i, N) scanf("%d %d", &v[i].a, &v[i].b); // 2. sort. sort(all(v)); // 3. dp更新. rep(i, N){ // 最後の注文以外(時刻 T - 1 まで). rep(j, T){ int t = j - v[i].a; dp[i + 1][j] = (t >= 0) ? max(dp[i][j], dp[i][t] + v[i].b) : dp[i][j]; } // 最後の注文(時刻 T). dp[i + 1][T] = max(dp[i][T], dp[i][T - 1] + v[i].b); } // 4. 出力. printf("%d\n", dp[N][T]); 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
[入力例] 2 60 10 10 100 100 [出力例] 110 ※AtCoderテストケースより [入力例] 3 60 10 10 10 20 10 30 [出力例] 60 ※AtCoderテストケースより [入力例] 3 60 30 10 30 20 30 30 [出力例] 50 ※AtCoderテストケースより [入力例] 10 100 15 23 20 18 13 17 24 12 18 29 19 27 23 21 18 20 27 15 22 25 [出力例] 145 ※AtCoderテストケースより [入力例] 6 8 1 1 3 5 2 3 4 6 1 2 3 3 [出力例] 17 [入力例] 15 100 12 47 63 60 22 58 81 30 77 115 66 61 77 83 6 99 5 80 89 41 33 16 18 112 22 44 18 28 55 67 [出力例] 555 [入力例] 50 1234 58 505 77 474 54 519 43 545 17 485 29 537 40 543 27 548 36 458 39 497 39 505 45 478 32 555 48 470 28 475 55 466 30 511 16 555 39 569 11 777 29 475 16 491 40 546 18 547 17 506 66 478 49 482 50 577 40 520 41 492 34 490 23 499 57 489 30 492 11 500 32 543 53 529 48 499 35 449 44 486 11 555 55 515 52 533 46 504 54 467 50 532 40 535 49 535 38 525 32 480 [出力例] 20000 |
■参照サイト
AtCoder Beginner Contest 145