C++の練習を兼ねて, 競プロ典型 90 問 の 問題037 (Don’t Leave the Spice) を解いてみた.
■感想.
1. 問題037は, 方針が見えなかったので, (問題037 (Don’t Leave the Spice) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 新しい知識として, スライド最小値 を, 確認できたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題037 を ご覧下さい.
■C++版プログラム(問題037／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 55 56 57 58 59 60 61 62 63 64 65 66 67 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/037.jpg // 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 pof pop_front #define pob pop_back #define pub push_back #define puf push_front int l[505], r[505]; LL v[505], dp[505][10101]; int main(){ // 1. 入力情報. int W, N; scanf("%d %d", &W, &N); rep(i, N) scanf("%d %d %lld", &l[i + 1], &r[i + 1], &v[i + 1]); // 2. dp更新(解説通り). rep(i, 505) rep(j, 10101) dp[i][j] = -1; dp[0][0] = 0; repx(i, 1, N + 1){ deque<int> dq; int k = r[i] - l[i] + 1; // 有効な区間幅. rep(j, W + 1){ // 選ばない場合. dp[i][j] = dp[i - 1][j]; // インデックスが有効か？ if(j < l[i]) continue; // スライド最小値. // https://phwinx.hatenablog.com/entry/2018/11/17/042646 // -> 先頭要素に, 最大値が保存されている状態を目指す. int cur = j - l[i]; while(!dq.empty()){ int e = dq.back(); if(dp[i - 1][e] <= dp[i - 1][cur]) dq.pob(); else break; } dq.pub(cur); int s = dq.front(); if(s + l[i] == j - k) dq.pof(); // deque が 空 になってないか？ if(dq.empty()) continue; // dp更新可能か？ s = dq.front(); if(dp[i - 1][s] == -1) continue; // 選ぶ場合. dp[i][j] = max(dp[i][j], dp[i - 1][s] + v[i]); } } // 3. 出力. printf("%lld\n", dp[N][W]); 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 162 163 164 165 166 |
[入力例] 100 4 30 40 120 30 40 30 30 40 1500 30 40 40 [出力例] 1660 ※AtCoderのテストケースより [入力例] 100 4 13 15 31415 12 13 92653 29 33 58979 95 98 32384 [出力例] -1 ※AtCoderのテストケースより [入力例] 5000 5 1000 1000 1000000000 1000 1000 1000000000 1000 1000 1000000000 1000 1000 1000000000 1000 1000 1000000000 [出力例] 5000000000 ※AtCoderのテストケースより [入力例] 10000 20 4539 6002 485976 1819 5162 457795 1854 2246 487643 1023 4733 393530 1052 6274 289577 1874 2436 167747 1457 4248 452660 2103 4189 174955 3057 5061 319316 4898 4953 394627 1313 2880 154687 1274 1364 259598 3866 5844 233027 1163 5036 386223 1234 4630 155972 2845 4978 442858 3168 5368 171601 3708 4407 394899 3924 4122 428313 2112 4169 441976 [出力例] 2727026 ※AtCoderのテストケースより [入力例] 10 2 1 1 3 3 3 5 [出力例] -1 [入力例] 10 3 1 1 3 3 3 5 6 6 5 [出力例] 13 [入力例] 17 5 1 1 3 3 3 5 5 5 2 7 7 4 9 9 8 [出力例] 15 [入力例] 300 10 18 87 15 117 206 14 40 140 7 41 76 3 119 123 11 61 157 13 10 17 3 74 193 18 106 193 10 48 81 3 [出力例] 63 [入力例] 2021 20 183 189 155689 130 137 1206900 153 156 525365 89 99 717566 208 216 888757 95 100 804792 34 43 189160 22 29 984929 87 94 970880 7 12 234533 109 118 1208356 80 86 337394 45 54 279909 84 87 1115989 15 20 443194 14 16 416494 22 31 1076301 93 97 1083443 30 34 58830 115 118 234045 [出力例] -1 [入力例] 2022 30 15 20 294055 15 24 671762 46 53 724087 95 102 498068 16 18 208208 18 25 313671 55 58 824721 108 112 206751 50 52 389291 108 110 384652 124 130 279184 85 87 24088 64 71 1182134 62 65 755468 114 119 1078425 23 32 410211 109 111 949466 88 97 497373 98 108 797655 68 74 876269 40 47 817773 34 40 901397 84 85 898356 123 124 253600 75 81 773194 107 109 281478 53 61 980821 21 29 629501 25 31 370663 112 120 125819 [出力例] 17374053 |
■参照サイト
037 – Don’t Leave the Spice
問題037 (Don’t Leave the Spice) 解説
スライド最小値