我连朴素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啦~

题目

Problem Description

Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has \(N\) words, and each word \(i\) has a cost \(C_i\) to be printed. Also, Zero know that print \(k\) words in one line will cost
\((\sum\limits_{k=1}^kC_i)^2+M\)
\(M\) is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

阅读更多