0 Judge
Code: 0
有一個陣列$a[1]\cdots a[N]$。現在要選擇其中的一些數,相鄰的有選到的數會形成一組,例如選了$a[2],a[3],a[4],a[5],a[7],a[10],a[11]$,會形成三組。請問所有選法當中,「選到的數的總和」乘以「組數」的最大值是多少?
第一行有一個正整數$N$。($1\leq N \leq 2000$)
第二行有$N$個正整數$a[1]\cdots a[N]$。($1\leq a[i] \leq 1000$)
所有選法當中,「選到的數的總和」乘以「組數」的最大值。
子任務一(10%):$1\leq N \leq 3$
子任務二(30%):$1\leq N \leq 17$
子任務三(60%):無特別限制
5
3 1 2 4 4
27
5
3 1 2 5 4
28
17
3 3 2 4 1 7 4 5 2 3 1 6 2 1 5 3 3
328
範例1:選擇$a[1],a[3],a[5]$,共形成三組,相乘為$9\times 3=27$。
範例2:選擇$a[1],a[3],a[4],a[5]$,共形成兩組,相乘為$14\times 2=28$。
範例3:唯一的最佳方案是選擇$a[1],a[2],a[4],a[6],a[8],a[10],a[12],a[13],a[15],a[17]$。