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啦~

【题解】玩具装箱toy BZOJ1010 斜率优化DP

萌萌哒传送门
自己做的斜率优化第一题,然而中途有点不记得了又翻了HDU3507的代码。。。还看了下别人的代码看会不会爆long long(其实对于不会爆long long这个问题我自己的证明好像不够严密,说白了就是乱想了一下,这种不严谨的东西就不写出来了)
然后,我没有想出二维DP方程来(雾),于是上网借鉴了一下。。。
(好吧这根本就不是自己做的了)
我怎么这么菜啊。。。

阅读更多

HDU3507 Print Article 斜率优化DP入门

题目

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.

阅读更多