BZOJ3675 APIO2014 序列分割 斜率优化

我连朴素DP方程都没想出来。。。
f[i][k]表示前i天分成k段的答案,那么就有
\(f[i][k]=f[j][k-1]+sum[j]\times (sum[i]-sum[j])(1\leq j\lt i)\)
然后根据前几天看的征途,把\(sum[j]\)看成是\(x\),把\(sum[i]\)看成\(k\),把\(f(j,k-1)-sum[j]^2\)看成\(y\),然后\(f(i,j)=y+k\times x\),维护一个最大值的凸包即可。
然后又抄了征途的代码。。。
看到网上说要考虑为0的问题,有的直接把0去掉了,我这样做交BZOJ上一直RE。
然后到UOJ上发现要输出方案,于是记录编号又不能去掉0的来记录。。。后面发现有一个点竟然第一个答案都输出了负数。
实在好烦了,就没有管0的事情了,把它当成一个普通的数来做。。。自测竟然没问题,交UOJ上,AC了!!!
然后去掉输出方案,交BZOJ上,AC了!!!
因为我斜率没有减法,所以可能不用考虑这个问题吧。(其实我以为我会97分的QAQ)
这题就A啦~