挑戰題

挑戰題1

風起時，書頁翻飛如陣陣嘆息，浩然圖書館內，歲月靜靜堆疊成知識的長河。
自1958年，那些沉默的書本，等待著，誰能為它們點燃新生的光。

向荷與昱君，肩負著求知的信念，踏入這座書海殿堂，望著滿架書卷，立下誓言：
「就算披星戴月，就算蠟燭成灰，我們也要將這裡的每一本書，悉數讀完。」

圖書館中共有

$n$ 本書，
而每本書蘊含不同深度的智慧，讀完所需時間分別為

$t_1,t_2,...,t_n$

館藏深處，流傳著一條古老的守則——
「每本書，只認一位讀者的眼睛，從開卷到終章，始終如一。
若有人中途接手，文字便會如煙消逝，知識將化為空白。」

沒人知道這規則從何而來，
有人說，是為了尊重書本的靈魂；
也有人說，是學者們對專注與恆心的最後考驗。

因此，她們只能分工而行，
一人一書，不可同時閱讀同本書，也不可交替。

她們知曉，這不僅是閱讀，
而是一場靜默的修行，一段孤獨卻無悔的旅程。

那麼，若兩人攜手分擔，遵循這既定的規則，
完成這場知識長征，所需的最短時間，究竟是多少？

輸入格式

第一行輸入有一個整數

$n$：書籍的數量。
第二行有

$n$ 個整數

$t_1,t_2,...,t_n$：閱讀每本書所需的時間。
值域:

$1\le n\le 2\cdot {10}^5,1\le t_i\le {10}^9$

輸出格式

$t_{total}$：最短總時間。

範例說明

輸入：

3
2 8 3

輸出：

16

閱讀順序分配方式(不一定只有一種分法):

• 向荷:
  $2\to 3\to 8$
• 昱君:
  $8\to 3\to 2$

在向荷讀完前兩本之後須等待昱君讀完第一本(耗時8)才能換她開始讀，因此總時間為16。
更多例子請參考測試資料。

提示

不要想太複雜
Estimate codeforces rating : 1000

測試資料

1

輸入:

3
7 6 4

輸出:
17

2

輸入:

10
1 2 3 4 5 6 9 8 7 16

輸出:
61

3

輸入:

10
1604 1666 1399 697 922 1328 1601 808 1189 11215

輸出:
22430

4

輸入:

10
525444 634998 619746 197023 43881 618674 652923 675599 407471 577298

輸出:
4953057

6

輸入:

2000
1206 4047 5623 4932 413 5265 7130 6049 4643 3753 1913 4549 300 664 1789 2754 7034 1415 2270 318 1380 167 9196 1598 403 8901 7916 6434 6255 7024 4112 7986 1194 7214 5899 9863 8619 3611 7795 8525 9949 3620 3896 8711 7529 9859 3779 6644 626 2012 8482 6161 1759 1095 5428 8063 3998 3759 1520 8726 6727 9130 2667 761 8559 730 1081 4988 4270 9988 4963 5876 3187 8798 4330 8207 6070 414 715 1396 7310 2897 9412 475 7780 5946 2886 4015 6856 411 8219 1827 6179 696 8729 2724 6445 8890 3704 2589 4255 1922 4241 3312 7995 4863 1912 6836 8251 8001 6539 5066 1112 6351 8107 6773 940 5654 3114 5785 5417 8802 6373 1618 3467 7186 1333 3896 8060 1959 5633 6338 1911 2062 3110 6585 5311 8895 9129 2558 5616 5108 908 6255 1654 6157 4175 2726 1950 1811 2297 3010 649 7612 5368 8138 1128 9184 4149 1455 4980 9 1451 2369 5325 944 3689 1989 4438 1173 2262 262 1694 414 4277 4106 6930 4837 5481 4630 7969 1131 8491 4180 4657 4257 2841 1123 5376 9625 1025 2048 6077 776 2303 6516 728 8687 5507 6366 4743 6250 3078 1763 3691 9417 8351 3843 2227 3645 913 2318 2607 5445 9927 7254 9607 425 227 4470 9949 2102 450 1171 5823 9036 2052 467 1874 3300 5499 9868 3964 183 9906 5805 3569 2731 1169 8466 1201 8110 382 5940 1455 6168 2245 4576 500 6540 9979 1770 2261 7023 2784 401 4291 5532 6659 9444 6194 7912 5242 8725 9900 7762 9330 3597 6966 8860 948 7056 339 9728 2057 3651 3784 2605 5727 3499 7937 6225 2812 9079 3410 8220 1330 785 4383 2514 4804 8993 336 8001 952 6947 415 6979 8957 4970 8740 1430 5007 9237 6195 8731 3433 7760 6388 1948 2523 4686 8116 145 460 5542 2010 6340 1265 7755 6301 3732 1726 2657 163 4167 3484 1853 4509 5636 7420 2220 2962 880 9147 5175 920 6854 1959 4741 6970 972 4961 2113 1767 4932 1219 3838 3127 9921 2404 1752 4147 8907 5385 909 7989 4900 9407 4076 5710 4731 4374 4572 151 3841 2736 1120 9498 7339 1642 6297 2450 1575 2778 301 3520 8722 8874 9735 2736 5385 1972 9295 6555 2031 3071 5612 8109 1038 6088 4790 1450 6769 500 5409 2813 3762 8085 3863 2513 9392 283 2757 8964 3539 4813 2617 5305 8387 8233 7002 4333 8741 7368 7448 523 7527 325 1094 8500 3007 9376 8486 921 2991 7502 579 2667 1979 2147 740 7846 6494 3938 4144 1864 1769 2852 1901 4648 2302 7895 798 5093 1117 2329 6588 5885 2397 950 5843 1888 7421 4222 193 9987 6138 8107 90 9577 2180 6513 9632 7279 5325 4150 178 5719 753 548 8146 9143 4812 4717 443 1410 4297 3535 4866 5304 4071 2536 5276 1914 7713 5755 1025 3505 7693 6067 879 6463 3172 184 7266 7125 6836 1792 7507 1543 99 1735 8047 7517 4533 6578 3257 8891 6880 5073 2050 1508 1486 6467 7272 6970 9666 974 9869 233 7870 3391 4041 4389 4421 4031 5379 9297 717 5991 4172 9569 2839 2117 5452 258 6049 5151 5185 2360 5355 2903 149 5593 7850 6848 8335 1897 9722 4288 8925 8996 5623 8647 3137 6403 9437 1871 4553 8537 926 1364 3444 6477 8820 2037 3681 4526 2680 364 9098 322 4098 395 7250 1487 9570 7111 7434 7981 9439 7513 3706 1451 4174 5890 8654 4769 5157 9391 382 7958 9088 4622 2755 932 243 2016 7671 2009 2017 5936 333 6031 7069 2786 4753 3182 4560 6175 464 8495 7194 7104 3035 4852 2716 2969 5240 967 8101 6921 7306 737 9403 2430 930 812 2732 4446 133 9995 390 1075 5616 9192 6116 1031 4602 3038 2234 3985 3017 392 4787 6926 3512 6521 1944 8755 4471 7390 2676 2194 307 7345 6502 8012 4792 7679 1495 4662 4324 8604 93 1550 4141 3189 5439 9648 2054 711 3513 7044 2078 2606 3602 5482 586 2145 8524 377 388 3948 8412 3124 9379 4925 2059 5615 9789 2308 4092 7104 9579 3556 7695 1385 6492 8927 4357 1637 5676 6993 2517 4577 4326 6059 2910 5917 1944 4707 6158 1523 5654 7002 4419 3959 8897 2383 944 7743 3834 226 5970 3622 5778 635 2964 5627 8483 5452 2847 6335 4580 7204 406 5135 3369 9814 4337 8783 2426 2793 8983 8600 8165 9361 466 4658 5478 4222 2302 694 6230 5107 7699 3469 6113 3994 2707 349 4556 9334 4933 486 5655 7801 1539 9991 2512 455 4625 2039 808 3354 8175 4576 9978 279 5905 4286 1817 6082 4013 6249 8745 910 4965 543 1553 7847 2469 5415 1615 819 8063 3777 7404 5302 4549 9745 9218 8245 5639 8285 3019 638 878 6213 76 3766 744 2083 6690 899 2693 8291 75 6971 5809 6148 1913 6476 995 8944 3490 6605 9268 5001 3340 9060 6805 7716 647 5434 4363 1994 2762 7261 5740 220 1603 4741 4574 9160 1114 1673 3693 7882 309 2914 622 6228 4785 8063 1299 4544 8175 8139 3470 357 3053 1260 4408 6553 8119 717 132 582 1518 367 144 8176 2936 2875 2108 6805 7719 9772 3871 8182 7534 9275 3222 1366 1074 2554 669 688 590 548 707 686 3913 2453 2201 1623 9883 2006 172 6104 4078 1004 2979 1607 1074 4290 5947 947 4148 2164 8817 5072 2927 8574 4239 2322 2227 8259 6827 264 885 8178 604 4235 2135 486 6527 2087 6650 893 4057 2489 6850 284 9101 1369 5481 1553 1041 4922 9654 345 5628 992 8431 9779 2194 1729 5772 9092 1763 1023 7838 4588 673 9429 8944 1577 5233 3664 3293 3723 9252 8304 2946 9383 4870 8271 9781 6448 230 1169 5735 2483 7368 9405 1846 3842 7959 6859 7014 1796 8975 3438 7152 2554 9082 1028 1643 2005 9368 4795 8843 6054 2805 7830 2631 7846 8150 5217 7295 9975 404 5073 9966 8506 1372 2031 8972 2627 294 695 7335 411 7925 4540 6996 1300 5278 9503 8080 3650 7020 7711 2028 4359 9651 1683 8408 2511 2772 598 8270 5118 177 6657 3235 6711 946 8848 1466 8286 310 7022 8666 2880 9582 4082 2464 9266 4902 7198 2184 8455 9477 1205 1272 2630 9848 654 8861 8587 9610 6598 7115 5773 6678 586 9743 5456 896 6389 8983 8348 4241 871 3476 1677 6417 1143 47 1340 5946 8331 5658 6734 5067 4021 6392 3004 5802 7407 351 6883 7198 891 7933 7820 3227 6164 8697 4239 4767 9449 9803 5091 6205 843 7551 4873 6872 3061 8694 7162 5986 59 3518 8862 5317 4230 2435 7903 578 319 853 2733 3881 7706 4524 9124 2728 2870 921 7082 7607 3842 4671 2781 7139 1250 9986 6140 889 5425 1519 7285 3254 1417 4092 8047 3261 929 305 7897 1288 1334 3351 5379 6738 9534 2080 1227 437 4825 5016 9147 3199 9176 1258 9360 1403 2739 3190 1983 9917 7621 4097 7011 8334 8843 6253 3098 6201 5933 1675 8304 8468 5340 1374 8588 6051 2653 5490 4890 9497 5252 125 121 1297 548 8628 1990 2941 8902 7345 1736 1372 7289 628 5325 6929 649 2184 5653 1874 3155 6840 8126 7774 1863 7297 4495 9138 8831 9337 2858 942 5856 1472 827 8691 9614 1078 4278 816 740 5950 336 4174 8628 545 428 4328 860 150 185 5055 1994 3024 1114 1677 7842 1272 838 9288 6397 2365 8785 5386 1908 2058 4923 5374 3517 4295 1815 1981 5589 1346 7247 8746 1327 7439 2502 2011 9836 653 9534 9258 107 7148 1932 3306 4851 3996 2648 8525 9167 247 3849 8565 1625 961 3360 5610 5962 6431 9411 5740 6496 8119 8606 1482 8865 9062 2645 2738 5344 3047 8301 3961 8942 290 9995 3677 9106 2244 557 377 284 8350 136 4105 630 5040 8226 9631 6140 4263 5553 3749 1150 9700 5075 276 211 2863 2240 5460 8097 2764 4988 5685 970 8765 1169 7854 4232 6104 797 9876 2845 8970 4488 7981 884 9996 8905 9173 7036 2565 713 5552 3574 65 5688 7297 3661 8753 814 8715 2374 7474 933 1382 9688 7506 4997 7093 8493 672 9664 8021 9273 1332 7424 8520 5595 9311 3149 4707 5426 1972 4579 5812 9041 967 6771 5145 5766 2500 9881 621 3704 3699 4766 2276 2383 1147 1311 9465 7560 2661 1822 4549 249 6051 1447 4707 8770 4240 8774 978 805 1113 519 1547 6391 8541 3022 3459 8567 5105 7400 5491 8414 1271 721 1094 9064 1247 2551 931 4514 3790 1999 6236 7476 1743 9975 5110 7362 424 6428 3162 1997 14 6653 7659 4639 5627 1967 7849 663 7262 3315 1685 1313 7796 4165 6534 6298 9063 4214 2571 4306 9092 523 3058 915 2880 6711 3417 5730 2973 5127 6243 6083 5626 2013 8637 210 6681 3968 2657 8911 5526 6786 8219 3545 4196 2225 1562 4446 9 9938 5049 2065 9677 2251 6495 7086 1935 3503 3971 107 8617 1184 8404 1167 1829 3152 6857 1399 6704 2216 9268 3958 7214 653 6460 9197 4702 399 5115 2123 1967 8116 5221 2023 1667 1477 3994 764 3 9719 7934 9668 9092 9277 9335 840 4968 7532 2582 9447 4008 2735 2266 4709 5504 6972 5665 4229 6859 9782 4865 666 8673 820 1222 4123 5566 1491 2812 4982 645 103 4352 7158 2212 4152 7458 8023 10 1834 2894 4697 4679 9917 2203 3859 8803 9783 4674 2011 8754 4302 9987 9043 1861 2107 4614 7414 8580 6715 7870 6563 8812 5223 7394 3800 9107 3383 5470 1123 7156 259 5527 4902 3655 5450 9438 2361 9679 6806 215 548 9019 7951 1163 637 197 5247 6539 8351 2303 1639 1125 588 4688 8256 6348 9923 8681 5684 6499 5109 764 9613 3338 7989 879 6622 7532 9423 2093 513 4136 5259 9598 3089 7807 3697 969 7194 8798 798 6103 6349 3276 1464 2617 7128 5621 495 5916 1525 3481 7669 9356 9762 1535 991 2375 3553 1550 812 772 9825 637 6198 8516 9372 8072 3654 6695 6882 2774 493 2658 3767 3754 784 5568 1752 9207 6195 9110 2516 5319 5818 1148 1480 445 1116 4712 4731 5290 3321 3533 4572 1805 3597 1572 4825 6078 805 4057 9697 4973 3346 9658 9643 726 5003 44 8489 1752 1272 1567 3096 4118 9293 6818 4761 2750 5747 537 3173 1288 1997 3422 2107 9313 6793 7879 302 2985 5398 9431 3006 9785 2677 9174 5331 1097 531 2869 4609 257 2917 8205 536 4558 4389 2904 1580 9016 5837 275 261 6354 145 417 3463 5489 8066 7091 6724 5920 1471 7815 624 3955 911 8287 9478 8811 333 1636 7674 9610 5731 8954 2174 8983 1195 1173 4825 2164 817 428 5748 3262 7628 8654 4423 5013 6031 4946 3380 749 2395 4979 2817 6579 3416 4620 1868 5476 1171 2560 3386 1515 650 9821 945 4009 9750 322 4903 5770 1992 5278 3915 757 9799 9195 8914 4916 7785 7724 2388 4838 5952 2546 1832 7409 7431 4645 2349 5276 9757 1553 4971 1099 9857 4591 8153 524 2191 3206 5904 226 2537 2417 4640 7391 1338 5570 8386 120 6759 2247 398 7060 7559 1837 829 3013 7604 9843 3601 2826 4898 4224 6564 308 3568 5895 2398 9847 6141 2377 8363 6579 3037 5515 8941 2148 6876 9930 5198 7895 3794 5885 728 9487 5351 6635 6024 6150 3225 540 3904 4247 891 340 4285 4508 6016 4141 5112 339 249 7315 7568 5463 7020 6022 9592 1052 374 2428 9229 634 9905 4854 1228 8462 5721 4884 6241 861 987 2074 8834 9931 8592 6597 701 8652 2233 281 6096 9096 6955 1661 9720 2628 4349 1466 507 558 1279 9071 1273 1385 749 3144 8112 1834 1620 5920 7824 4610 2229 5861 7872 702 8808 9387 3134 7275 194 4116

輸出:
9235765

7

如果都答對了，算你厲害

答案程式碼(寫完再看)

#include <bits/stdc++.h>
using namespace std;
int main(){
    //不告訴你呵呵，真的寫出來了記得告訴我
    //應該不會超過20行
}

Problem Source

挑戰題2

在浩然圖書館最隱密的閣樓上，存放了一排神奇的古籍。經過研究，向荷與昱君發現這些書籍是擁有靈性的知識載體，每本書上都刻著一個數字代表其靈氣強度。而閣樓有個古老的守則
「在一次的閱讀中，這些古籍必須保持原有的排列順序，卻可以分配給不同讀者。每位讀者閱讀書籍時必須符合其心性——或漸進提升，或深入淺出。若違背規則，文字便會如煙消逝，知識將化為空白。」

向荷和昱君性格迥異。昱君性如清泉，思維漸進，喜歡循序漸進地吸收知識，適合靈氣由小到大的閱讀書籍；向荷則如山峰巍峨，思想跳脫，善於從複雜到簡單地歸納總結，更適合靈氣由強到弱的閱讀書籍。

然而在每次的閱讀向荷與昱君都會消耗大量心神，因此需要來罐 redbull 才能恢復體力。她們的 redbull 有限，因此必須設法用最少的次數共同讀完所有書籍，將寶貴的 redbull 用在刀口上。

任務描述

你被向荷與昱君委託協助完成這項任務：
你要將這些古籍

$M$ 分配整理成最少數量的閱讀序列，使得：

1. 適合向荷的閱讀序列靈氣值逐漸增大（符合她漸進的性格）
2. 適合昱君的閱讀序列靈氣值逐漸減小（符合她歸納的思維）
3. 每本書只能分配給一位讀者
4. 書籍必須保持原有的擺放順序
5. 閱讀序列的總數必須最少（以節省寶貴的 redbull）

輸入格式

第一行輸入有一個整數

$n$：書籍的數量。
第二行有

$n$ 個整數

$M_1,M_2,...,M_n$：表示每本書的靈氣強度值，皆相異
值域:

$1\le n\le 25,1\le M_i\le 100$

輸出格式

輸出有一個整數

$k$：最少要幾瓶 redbull。

範例說明

輸入：

6  
5 2 9 4 7 1

輸出：

3   

將

$[5,2,9,4,7,1]$ 分成三個閱讀序列(不一定只有一種分法)：

• 第一個序列包含
  $[5,9]$（靈氣值遞增，適合向荷）
• 第二個序列包含
  $[2,1]$（靈氣值遞減，適合昱君）
• 第三個序列包含
  $[4,7]$（靈氣值遞增，適合向荷）

這樣向荷與昱君只需 3 瓶 redbull，便能完成所有古籍的閱讀。
更多例子請參考測試資料。

提示(先想一下別直接看)

題目白話文 : 給定一個整數數列，你需要將它拆成若干個子序列，使得每個子序列要麼嚴格遞增，要麼嚴格遞減，且總數最少。(NP-Hard 問題)
真的寫出來了記得告訴我，請你喝飲料

Estimate codeforces rating : 1400

策略(再想一下別直接看)

DFS+剪枝

測試資料

1

輸入:

5
1 2 3 4 5

輸出:
1

2

輸入:

5
5 4 3 2 1

輸出:
1

3

輸入:

5
1 4 2 3 5

輸出:
2

4

輸入:

10
1 3 5 10 8 6 7 9 4 2

輸出:
2

5

輸入:

15
7 34 83 57 25 35 38 67 88 75 15 98 54 63 73

輸出:
3

6

輸入:

20
1 3 5 7 9 11 13 20 18 16 14 12 15 17 19 10 8 6 4 2

輸出:
2

7

輸入:

25
39 5 19 3 45 89 25 56 37 55 63 58 17 65 23 96 74 32 9 31 66 61 99 3 77

輸出:
4

8

輸入:

25
19 21 23 13 2 20 24 9 8 1 10 6 18 5 15 7 11 16 25 3 12 4 22 17 14

輸出:
5

9

你很厲害你很厲害你很厲害你很厲害你很厲害你很厲害你很厲害

答案程式碼(寫完再看)

這是較好理解的寫法，還有優化空間勿噴(NP-Hard 問題)

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

int n, ans = INT_MAX;
vector<int> arr;

void dfs(int idx, vector<pair<vector<int>, bool>> &seqs) {

    if (seqs.size() >= ans)
        return;

    if (idx == n) {
        ans = min(ans, (int)seqs.size());
        return;
    }

    int curr = arr[idx];

    vector<pair<vector<int>, bool>> ori_seqs = seqs;

    for (int i = 0; i < seqs.size(); ++i) {
        vector<int> &curseq = seqs[i].first;
        bool is_incr = seqs[i].second;
        int last = curseq.back();

        if (is_incr && curr > last) {
            curseq.pb(curr);
            dfs(idx + 1, seqs);
            seqs = ori_seqs;
        } else if (!is_incr && curr < last) {
            curseq.pb(curr);
            dfs(idx + 1, seqs);
            seqs = ori_seqs;
        }
    }

    seqs.pb(make_pair(vector<int>{curr}, true));
    dfs(idx + 1, seqs);
    seqs = ori_seqs;

    seqs.pb(make_pair(vector<int>{curr}, false));
    dfs(idx + 1, seqs);
    seqs = ori_seqs;
}

int main() {
    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    ans = n;
    vector<pair<vector<int>, bool>> seqs;
    dfs(0, seqs);
    cout << ans << endl;
    return 0;
}

沒了

沒人發現挑戰題1測試資料5不見了嗎