原題來自：APIO 2010

你有一支由 n 名預備役士兵組成的部隊，士兵分別編號為 1…n，要將他們拆分成若干特別行動隊調入戰(zhàn)場。出于默契的考慮，同一支特別行動隊中隊員的編號應該連續(xù)，即為形如 (i,i+1,…,i+k) 的序列。 編號為 i 的士兵的初始戰(zhàn)斗力為 x_i ，一支特別行動隊的初始戰(zhàn)斗力 x 為隊內士兵初始戰(zhàn)斗力之和，即 x=x_i+x_i+1+?+x_i+k。

通過長期的觀察，你總結出一支特別行動隊的初始戰(zhàn)斗力 x 將按如下經(jīng)驗公式修正為 x′:x′=ax²+bx+c ，其中 a,b,c 是已知的系數(shù)(a<0)。 作為部隊統(tǒng)帥，現(xiàn)在你要為這支部隊進行編隊，使得所有特別行動隊修正后戰(zhàn)斗力之和最大。試求出這個最大和。

例如，你有 4 名士兵， x₁=2,x₂=2,x₃=3,x₄=4 。經(jīng)驗公式中的參數(shù)為 a=–1,b=10,c=–20。此時，最佳方案是將士兵組成 3 個特別行動隊：第一隊包含士兵 1 和士兵 2，第二隊包含士兵 3，第三隊包含士兵 4。特別行動隊的初始戰(zhàn)斗力分別為 4,3,4，修正后的戰(zhàn)斗力分別為 4,1,4。修正后的戰(zhàn)斗力和為 9，沒有其它方案能使修正后的戰(zhàn)斗力和更大。

輸入由三行組成。

第一行包含一個整數(shù) n，表示士兵的總數(shù)。

第二行包含三個整數(shù) a,b,c，經(jīng)驗公式中各項的系數(shù)。

第三行包含 n 個用空格分隔的整數(shù) x₁,x₂,…,x_n，分別表示編號為 1,2,…,n 的士兵的初始戰(zhàn)斗力。

數(shù)據(jù)范圍與提示：

20% 的數(shù)據(jù)中，n≤1000；

50% 的數(shù)據(jù)中，n≤10⁴ ；

100% 的數(shù)據(jù)中，1≤n≤10⁶,–5≤a≤–1,∣b∣,∣c∣≤10⁷,1≤x_i≤100。

信息學一本通 動態(tài)規(guī)劃