o079.
4. 最佳選擇
內容
給一個長度為 $n$ 的正整數序列 $a_1, a_2, \dots, a_n$，你可以執行多次操作 (包含 0 次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。
求滿足總和不超過 $k$ 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。
輸入說明
第一行輸入兩個正整數 $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 分): 無限制
輸出說明
輸出滿足題目需求的最大值。
範例輸入
#1
8 22 1 5 2 2 9 3 5 8
範例輸出
#1
16
範例輸入
#2
7 20 7 7 8 2 8 9 5
範例輸出
#2
0
測資資訊：
記憶體限制：
256
MB
提示 ：
範測 1:
1 5 2 2 9 3 5 8
選擇紅色數字，總和為 $16$
範測 2:
沒有任何符合題目條件的選法，總和為 $0$
標籤:
出處:
2024年6月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 40906 |
|
o079 | 1535 | 2024-06-17 14:43 | |
| 40913 |
|
o079 | 767 | 2024-06-17 17:08 | |
| 40919 |
|
o079 | 533 | 2024-06-17 22:43 | |
| 42018 |
|
o079 | 153 | 2024-09-20 20:15 | |
| 41634 |
|
o079 | 182 | 2024-08-12 16:04 |