【BZOJ3675】【APIO2014】序列分割 [斜率优化DP]

时间:2022-01-21 03:23:46

  在样例中,小H可以通过如下3轮操作得到108分:
  1.开始小H有一个序列(4,1,3,4,0,2,3)。
  小H选择在第1个数之后的位置将序列分成两部分,并得到4×(1+3+4+0+2+3)=52分。
  2.这一轮开始时小H有两个序列:(4),(1,3,4,0,2,3)。
  小H选择在第3个数字之后的位置将第二个序列分成两部分,并得到(1+3)×(4+0+2+3)=36分。
  3.这一轮开始时小H有三个序列:(4),(1,3),,(4,0,2,3)。
  小H选择在第5个数字之后的位置将第三个序列分成两部分,并得到(4+0)×(2+3)=20分。
  经过上述三轮操作,小H将会得到四个子序列:(4),(1,3),(4,0),(2,3)并总共得到52+36+20=108分。