C++の練習を兼ねて, 競プロ典型 90 問 の 問題011 (Gravy Jobs) を解いてみた.
■感想.
1. 問題011は, 解答の方針が見えなかったので, (問題011 (Gravy Jobs) 解説) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題011 を ご覧下さい.
■C++版プログラム(問題011／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://github.com/E869120/kyopro_educational_90/blob/main/editorial/011-02.jpg // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using T3 = tuple<int, int, LL>; #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 all(x) x.begin(), x.end() LL dp[5050][5050]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vector<T3> v; rep(i, N){ int d, c; LL s; scanf("%d %d %d", &d, &c, &s); v.emplace_back(d, c, s); } // 2. sort. sort(all(v)); // 3. dp更新. repx(i, 1, N + 1){ int d = get<0>(v[i - 1]); int c = get<1>(v[i - 1]); LL s = get<2>(v[i - 1]); repx(j, 1, 5050){ dp[i][j] = dp[i - 1][j]; if(j >= c && j <= d) dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + s); } } // 4. 集計. LL ans = 0; rep(i, 5050) ans = max(ans, dp[N][i]); // 5. 出力. 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 |
[入力例] 1 12 3 69853 [出力例] 69853 ※AtCoderテストケースより [入力例] 3 7 3 200000 3 2 100000 5 3 150000 [出力例] 350000 ※AtCoderテストケースより [入力例] 8 376 640 602876667 4015 1868 533609371 3330 152 408704870 1874 798 30417810 2 1450 40706045 3344 1840 801881841 2853 1229 5235900 458 1277 997429858 [出力例] 1744196082 ※AtCoderテストケースより [入力例] 20 376 640 602876667 4015 868 533609371 3330 152 408704870 1874 798 30417810 2 450 40706045 3344 840 801881841 2853 229 5235900 458 277 997429858 1689 948 981897272 4774 393 997361572 4237 750 294800444 4663 293 277667068 2249 808 444906878 3341 137 845317003 3625 765 739689211 911 510 326127348 1343 193 235655766 842 323 406413067 1425 303 68833418 212 808 745744264 [出力例] 6583558066 ※AtCoderテストケースより [入力例] 30 376 140 602876667 4015 368 533609371 3330 152 408704870 1874 298 30417810 2 450 40706045 3344 340 801881841 2853 229 5235900 458 277 997429858 1689 448 981897272 4774 393 997361572 4237 250 294800444 4663 293 277667068 2249 308 444906878 3341 137 845317003 3625 265 739689211 911 10 326127348 1343 193 235655766 842 323 406413067 1425 303 68833418 212 308 745744264 3563 376 196296968 4186 323 275217640 332 361 337078801 4466 245 694789156 3763 250 432518459 2937 124 581390864 2255 227 642944345 2851 480 688009163 1957 295 5532462 3277 445 15791361 [出力例] 11420667389 ※AtCoderテストケースより [入力例] 5 16 5 14 9 5 8 3 3 3 7 6 12 12 8 13 [出力例] 30 ※ 実際, 以下のスケジュールで, 報酬 30円 になる. 1 ～ 3日目 = 3 4 ～ 11日目 = 13 12 ～ 16日目 = 14 [入力例] 10 25 16 58 7 3 73 10 6 80 19 8 67 13 10 19 30 13 105 17 9 90 24 20 88 17 15 120 23 12 111 [出力例] 325 ※ 実際, 以下のスケジュールで, 報酬 325円 になる. 1 ～ 3日目 = 73 4 ～ 9日目 = 80 10 ～ 17日目 = 67 18 ～ 30日目 = 105 |