C++の練習を兼ねて, AtCoder Beginner Contest 145 の 問題F (Laminate) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 145 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://img.atcoder.jp/abc145/editorial.pdf // 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--) const LL INF = 202020202020202020; LL dp[303][303], h[303]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) scanf("%lld", &h[i + 1]); // 2. 初期化. rep(i, N + 1) repx(j, 1, N + 1) dp[i][j] = INF; repx(i, 1, N + 1) dp[i][1] = h[i]; // 3. dp更新. LL ans = INF; repx(x, 1, N + 1){ // 最も右の項の番号が, x で, 削除しない項の集合サイズが, y の 時. repx(y, 2, x + 1) repx(i, y - 1, x) dp[x][y] = min(dp[x][y], dp[i][y - 1] + max(0LL, h[x] - h[i])); // 最小値更新. ans = min(ans, dp[x][N - 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 |
[入力例] 4 1 2 3 4 1 [出力例] 3 ※AtCoderテストケースより [入力例] 6 2 8 6 9 1 2 1 [出力例] 7 ※AtCoderテストケースより [入力例] 10 0 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 [出力例] 4999999996 ※AtCoderテストケースより [入力例] 5 0 1 2 3 4 5 [出力例] 5 [入力例] 25 5 9 5 10 11 1 13 9 6 1 9 7 14 3 12 3 6 10 12 3 2 1 2 7 6 8 [出力例] 33 [入力例] 100 10 110 127 132 54 129 154 141 161 103 115 129 79 156 174 138 102 114 101 112 129 140 123 137 68 90 83 132 121 147 145 85 149 153 58 149 117 151 156 127 135 167 167 152 56 68 115 78 105 152 76 141 71 145 127 151 70 104 111 123 68 63 76 66 75 125 149 54 153 61 65 64 188 78 113 84 185 162 124 145 137 138 153 73 96 127 161 137 50 108 98 127 134 116 80 153 106 151 62 99 95 [出力例] 1234 [入力例] 300 77 682 884 1295 1125 1328 725 1635 623 1019 1447 855 1361 859 676 670 1736 1032 1062 1411 1648 974 555 812 542 1129 1638 1618 1720 513 575 1067 521 725 1000 1336 1592 1214 532 1089 782 1067 1741 604 1503 591 1584 971 1039 1240 1638 1169 739 1683 730 1545 1666 838 1243 1341 1140 576 829 1155 552 514 1728 522 721 1083 560 992 1262 982 865 556 1046 703 1040 1225 1367 785 1465 868 566 1507 572 1704 1654 862 1050 881 774 973 1181 1224 997 986 662 1379 803 651 1189 663 1640 1458 902 747 1398 1076 1457 1284 1749 1018 641 1182 1215 797 1289 1395 1062 1000 1027 1013 1019 1424 1739 1714 1610 799 620 1344 1196 1315 798 1000 773 909 1188 861 1540 1331 795 836 1000 1263 893 599 1249 1290 1404 1117 1265 1584 1340 1545 981 1320 903 851 1239 666 1029 612 1325 764 1369 984 1164 867 1368 556 1136 1019 1119 1035 604 1052 858 734 656 1253 1487 1371 864 1324 1000 943 679 1120 510 1000 547 1605 1029 610 1183 1339 1500 843 820 756 834 1565 526 1123 1719 603 1581 761 1654 1346 974 643 1400 543 1749 1168 782 1258 836 1297 1379 1375 1521 1319 1312 1698 1617 1347 1009 616 1038 1281 775 1267 1619 1015 826 1000 780 1012 1404 833 880 999 766 1085 601 1114 1036 1000 636 1004 1658 1048 1694 768 1166 828 1033 1366 1020 1252 1564 524 1456 687 1634 1109 506 1395 934 1498 1704 1000 1639 557 967 1009 1249 1440 1691 1450 1660 987 774 1569 1596 1453 1639 1734 673 1282 1187 549 1430 1149 1367 959 994 [出力例] 23456 |
■参照サイト
AtCoder Beginner Contest 145