[問題] 想請教個題目

[yuscvscv (小可魚)]

遇到的問題： (題意請描述清楚)

給你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
→ yuscvscv:如果題目敘述不清麻煩推文提出  謝謝
推 ckclark:怎麼覺得每個人都各自一組是最佳解
補個sample，sample就不是嚕
→ tropical72:聽起來像是 SOM 可以解決的東西..
→ yuscvscv:SOM 類神經網路算法?   這是高中競賽 感覺沒那麼複雜吧(?
※ 編輯: yuscvscv        來自: 111.255.28.138       (05/09 23:50)
→ tropical72:好奇追問：N=54,-> 53, 54, 1, 2, 算連續可分為一組嗎
→ yuscvscv:不行
→ tropical72:好想請你分享你的解法丫..
→ yuscvscv:如果我會了我還要問嗎Orz....
→ yuscvscv:N^2 大概就狀態 dp[i][j] 到第i個人時分j組的最優情形
→ yuscvscv:沒很仔細思考過 可能有誤
推 ckclark:那c>0的時候 各自一組是最佳解吧
→ justdemon:c>0各自一組也不見得會是最佳解  要看二次函數的最大值
推 ckclark:因為xi是正的 所以愈大的group^2*a就會扣愈多 還少了很多c
推 justdemon:那是因為你假設最大值發生在x<0的地方
→ yuscvscv:在某強者板上有看到線性解了 感謝各位幫忙的大大
推 justdemon:我道歉一下  ckclark是對的  XD
→ yuscvscv:嗯 這題條件鎖很死
推 justdemon:可以麻煩轉錄一下解答嗎?
→ yuscvscv:唔 還在驗證中......基本上是用DP加上本題的單調性