C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題C (最高のトッピングにしような) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. なお, 初回提出版では, MLE(メモリ制限超過)となったので, MLE回避するように修正して, 再提出している.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 027 解説 を ご覧下さい.
■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 39 40 41 42 43 44 45 46 47 48 49 50 |
// 解き直し. // https://www.slideshare.net/chokudai/arc027 // 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--) LL dp[303][606], pd[303][606]; // dp[303][303][606] だと, MLE となるので, 修正. int t[303], h[303]; int main(){ // 1. 入力情報. int X, Y, N; scanf("%d %d %d", &X, &Y, &N); rep(i, N) scanf("%d %d", &t[i], &h[i]); // 2. dp更新. rep(i, N){ // 初期化. rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = -1; pd[0][0] = 0; // 前回分反映. rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = max(pd[j][k], dp[j][k]); // 今回分反映. rep(j, min(i + 1, X)){ rep(k, X + Y + 1){ int nk = k - t[i]; if(nk >= 0 && pd[j][nk] != -1){ dp[j + 1][k] = max(dp[j + 1][k], pd[j + 1][k]); dp[j + 1][k] = max(dp[j + 1][k], pd[j][nk] + h[i]); } } } } // 3. 最大値. LL ans = 0; rep(j, X + 1) rep(k, X + Y + 1) ans = max(ans, dp[j][k]); // 4. 出力. 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 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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
[入力例] 3 5 4 3 30 3 40 5 60 7 80 [出力例] 100 ※AtCoderテストケースより [入力例] 3 3 4 3 30 3 40 5 60 7 80 [出力例] 70 ※AtCoderテストケースより [入力例] 1 5 4 3 30 3 40 5 60 7 80 [出力例] 60 ※AtCoderテストケースより [入力例] 6 12 4 3 30 3 40 5 60 7 80 [出力例] 210 ※AtCoderテストケースより [入力例] 1 1 1 1 11 [出力例] 11 [入力例] 7 15 10 7 100 2 33 6 66 4 44 8 55 1 9 12 111 10 178 7 77 5 55 [出力例] 333 [入力例] 12 33 25 3 642 2 174 10 129 6 1234 12 471 18 1013 10 207 6 642 3 1034 11 516 3 1075 9 201 9 1056 7 198 6 121 2 515 19 234 20 1111 3 924 5 770 2 677 4 1060 6 298 3 839 12 1010 [出力例] 10000 [入力例] 32 123 50 5 2237 11 527 12 69740 2 22416 8 77783 5 105904 12 122429 15 36253 7 115045 7 22468 12 108751 20 105233 4 34947 13 69463 5 5796 12 69023 3 31396 19 64113 8 30591 2 112723 7 113855 5 74920 17 63139 10 123438 19 26368 18 114828 3 8975 12 92652 25 117114 13 82653 5 106809 11 94419 17 54726 19 85275 16 91535 10 115684 7 101791 8 91513 3 122995 6 5408 7 79431 8 48599 19 115048 20 106513 11 64312 5 6456 7 102500 3 27527 19 23909 15 2042 [出力例] 2000000 |
■参照サイト
AtCoder Regular Contest 027