你是一位擁有由 $n$ 個士兵組成的部隊司令官,而士兵的編號為 $1 \sim n$。
為了即將到來的戰役,你計畫將這 $n$ 個士兵分成數個突擊單位。
為了凝聚士氣,每個單位將由連續序列(如 $i, i+1, \cdots, i+k$)的士兵組成。
每個士兵 $i$ 都有其戰鬥力評分 $x_i$。原先,每個突擊單位的戰鬥力總和為 $x$,
其計算方式是將每位士兵的戰鬥力相加,也就是說,$x = x_i + x_{i+1} + \cdots + x_{i+k}$。
然而,過去輝煌勝利的經驗告訴你,一個突擊單位的戰鬥力總和應該修正為修正戰鬥力 $x’$,
其計算公式為 $x’ = ax ^ 2 + bx + c$,而 $a, b, c$ 是已知係數($a < 0$),$x$ 是這個單位的原本戰鬥力。
身為一個司令官,你的任務就是將士兵們分配成數個突擊單位,確保所有單位的修正戰鬥力總和為最大值。
假設你有 $4$ 個士兵,$x_1 = 2, x_2 = 2, x_3 = 3, x_4 = 4$。
接著,藉由公式的係數改變該單位的戰鬥力,其中係數 $a = -1, b = 10, c = -20$。
在這個情況下,最好的方式是將所有士兵分成三個戰鬥單位:
第一個單位包含士兵 $1$ 和 $2$、第二個單位包含士兵 $3$、第三個單位包含士兵 $4$。
這三個單位的戰鬥力總和將分別為 $4, 3, 4$,而修正後的戰鬥力總和為 $4, 1, 4$。
這種分配方式的總修正戰鬥力將為 $9$,而且這是最好的分法。
輸入共有三列,第一列包含一個正整數 $n$,也就是所有士兵總數。
第二列包含三個整數 $a, b, c$,為公式中為了調整突擊部隊戰鬥力的係數。
最後一列包含 $n$ 個整數 $x_1, x_2, \cdots , x_n$,以空格隔開,分別代表著第一位士兵、第二位士兵、到第 $n$ 位士兵。
輸出一個整數,代表可達到最大的修正戰鬥力總和。
2021.04.09 Update: Added $\LaTeX$ and updated constraints by FHVirus
原TIOJ1745 / APIO '10
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |