[問題] 想請教個題目
遇到的問題： (題意請描述清楚)
給你N個人，然後他們的編號依序是1~N，第i個人有個戰鬥力Xi。
然後你要把他們分組，每個組內的成員編號必須連續，
且所有人都要有組，組數量不限。
然後每個組的戰鬥力為該組的成員Xi總和x，
此時我們給個校正公式，設這組的修正戰鬥力為 x' ， x' = ax^2 + bx + c。
然後要問你最大的"修正後的各組戰鬥力總和"。
會給你N, a, b, c以及各個Xi。
N < 1000000, -5 <= a <= -1, |b|和|c|皆 <= 10000000, 1 <= Xi <= 100
Sample Input
4 //N
-1 10 -20 //a, b, c
2 2 3 4 //Xi ( i = 1~4)
Sample Output
9
分組為
[2 2] [3] [4]
補充說明：
已有N^2算法，但想不出更高效的算法，麻煩板上的大大幫忙，感謝~
//N^2是利用動態規劃
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.28.138
→
05/09 23:11, , 1F
05/09 23:11, 1F
推
05/09 23:30, , 2F
05/09 23:30, 2F
補個sample，sample就不是嚕
→
05/09 23:31, , 3F
05/09 23:31, 3F
→
05/09 23:47, , 4F
05/09 23:47, 4F
※ 編輯: yuscvscv 來自: 111.255.28.138 (05/09 23:50)
→
05/10 00:00, , 5F
05/10 00:00, 5F
→
05/10 00:03, , 6F
05/10 00:03, 6F
→
05/10 00:16, , 7F
05/10 00:16, 7F
→
05/10 00:21, , 8F
05/10 00:21, 8F
→
05/10 00:22, , 9F
05/10 00:22, 9F
→
05/10 00:23, , 10F
05/10 00:23, 10F
推
05/10 00:24, , 11F
05/10 00:24, 11F
→
05/10 00:33, , 12F
05/10 00:33, 12F
推
05/10 00:37, , 13F
05/10 00:37, 13F
推
05/10 00:41, , 14F
05/10 00:41, 14F
→
05/10 00:44, , 15F
05/10 00:44, 15F
推
05/10 00:46, , 16F
05/10 00:46, 16F
→
05/10 00:47, , 17F
05/10 00:47, 17F
推
05/10 00:48, , 18F
05/10 00:48, 18F
→
05/10 00:51, , 19F
05/10 00:51, 19F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章