原題來(lái)自:HDU 3507
給出 $N$ 個(gè)單詞,每個(gè)單詞有個(gè)非負(fù)權(quán)值 $C_i$ ,現(xiàn)要將它們分成連續(xù)的若干段,每段的代價(jià)為此段單詞的權(quán)值和的平方,還要加一個(gè)常數(shù) $M$,即 $(\\sum C_i)^2+M$。現(xiàn)在想求出一種最優(yōu)方案,使得總費(fèi)用之和最小。
包含多組測(cè)試數(shù)據(jù),對(duì)于每組測(cè)試數(shù)據(jù):
第一行包含兩個(gè)整數(shù) $N$ 和 $M$。
第二行為 $N$ 個(gè)整數(shù)。
輸出僅一個(gè)整數(shù),表示最小的價(jià)值。
5 5 5 9 5 7 5
230
數(shù)據(jù)范圍與提示:
對(duì)于全部數(shù)據(jù),$0\\le N\\le 5 × 10^5,0\\le M\\le 1000$。