o079.
4. 最佳選擇
Content
給一個長度為 $n$ 的正整數序列 $a_1, a_2, \dots, a_n$，你可以執行多次操作 (包含 0 次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。
求滿足總和不超過 $k$ 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。
Input
第一行輸入兩個正整數 $n, k (1 \le n \le 3 \times 10^5, 1 \le k \le 10^9)$。
第二行有 $n$ 個正整數 $a_1, a_2, \dots, a_n (1 \le a_i \le 5 \times 10^3)$。
保證 $\forall i \in [1, n]$，前 $i$ 個數字的奇數和偶數數量差距不超過 $2 \times 10^3$。
(20 分): $n = 10^3$
(80 分): 無限制
Output
輸出滿足題目需求的最大值。
Sample Input
#1
8 22 1 5 2 2 9 3 5 8
Sample Output
#1
16
Sample Input
#2
7 20 7 7 8 2 8 9 5
Sample Output
#2
0
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint ：
範測 1:
1 5 2 2 9 3 5 8
選擇紅色數字，總和為 $16$
範測 2:
沒有任何符合題目條件的選法，總和為 $0$
Tags:
出處:
2024年6月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| ID | User | Problem | Subject | Hit | Post Date |
| 40906 |
|
o079 | 2046 | 2024-06-17 14:43 | |
| 40913 |
|
o079 | 1011 | 2024-06-17 17:08 | |
| 40919 |
|
o079 | 784 | 2024-06-17 22:43 | |
| 46250 |
|
o079 | 32 | 2025-06-09 23:41 | |
| 42018 |
|
o079 | 395 | 2024-09-20 20:15 |