C++の練習を兼ねて, 競プロ典型 90 問 の 問題019 (Pick Two) を解いてみた.
■感想.
1. 問題019は, 解答の方針が見えなかったので, (問題019 (Pick Two) 解説) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(本問では, 区間DP)の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題019 を ご覧下さい.
■C++版プログラム(問題019／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/019.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--) LL a[404], dp[404][404]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); int n = 2 * N; rep(i, n) scanf("%lld", &a[i]); // 2. dp更新(解説通り). // [l, r]の人だけが抜けるために必要な最小コスト. // 区間の長さ d が, 小さい順に計算していく. rep(l, n) repx(r, l + 1, n) dp[l][r] = 2020202020; repex(d, 1, n, 2){ rep(i, n){ // 2-1. 区間[l, r] を 設定. int l = i; int r = l + d; // 2-2. 区間[l, r] が 妥当であるかチェック. // -> 02_random_0.txt などで, WA となった理由と理解. if(r >= n) continue; // 2-3. 最後に, l + 1, ... , r - 1 が 抜ける場合. dp[l][r] = dp[l + 1][r - 1] + abs(a[l] - a[r]); // 2-4. それ以外の場合. repx(k, l + 1, r - 1) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]); } } // 3. 出力. printf("%lld\n", dp[0][n - 1]); 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 |
[入力例] 3 6 2 3 9 8 6 [出力例] 2 ※AtCoderテストケースより [入力例] 3 1 3 5 5 3 1 [出力例] 0 ※AtCoderテストケースより [入力例] 4 1 2 4 8 16 32 64 128 [出力例] 85 ※AtCoderテストケースより [入力例] 15 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 [出力例] 207 ※AtCoderテストケースより [入力例] 1 1 2 [出力例] 1 [入力例] 5 31 41 59 26 53 58 97 93 23 84 [出力例] 47 [入力例] 10 264 575 131 106 45 90 590 501 615 753 639 260 425 710 259 18 308 24 501 803 [出力例] 1429 [入力例] 50 84 84 116 105 20 10 45 51 0 104 15 47 78 26 101 92 76 47 96 45 108 3 119 49 74 49 64 73 14 96 51 42 16 119 111 41 108 53 88 77 62 7 88 81 11 65 116 91 40 92 108 77 116 49 117 29 36 76 49 46 76 17 33 23 59 74 36 27 1 95 30 120 106 113 109 30 46 17 114 13 2 26 27 0 32 47 121 58 11 85 31 86 79 79 92 82 14 23 37 90 [出力例] 618 [入力例] 100 95718 84211 5580 110309 97223 51987 98302 61798 19405 28227 31598 119044 45574 97347 83910 25608 19029 50278 101326 111364 91569 15702 44444 41011 119737 77777 92529 94730 114785 11111 90312 74058 121212 18155 122094 43162 33467 58431 11847 15409 79108 121306 116104 82917 60366 105221 82862 50846 31856 59924 107852 20984 112990 45907 105354 121778 26241 88446 85280 51981 2059 105918 116779 109910 82479 94077 71585 498 16291 116900 59901 1285 44875 110405 191919 92487 27667 90886 40752 61757 104421 90048 36276 99588 98668 111228 10922 47195 171717 55555 44239 181818 49837 25246 111111 37203 119593 116633 118803 12117 99617 101010 98919 110269 121298 18222 28549 100352 7035 65622 92151 83692 62514 100064 108345 3437 7223 20471 79006 99999 102996 53159 2731 93050 88888 120509 24734 98317 113659 7307 53069 161616 44184 23999 62345 2751 22105 43533 41363 76363 6796 46149 59836 107606 113362 69022 66666 100458 151515 22332 40872 100065 77941 68058 67841 108211 119605 24657 35990 73405 33953 202020 76112 27677 99916 64955 33333 3697 116214 90340 0 28684 37209 59448 44936 60426 67151 13235 72217 24709 12312 111258 98241 141414 22222 41091 21776 131313 29043 14612 53652 90915 8309 54132 60738 56930 122374 81458 4729 73764 [出力例] 1278528 |