斜率优化复习笔记

学习笔记

快省选了,感觉自己dp像是什么都没有学一样,还是tcl.

适用范围

就是转移式子和$i$,$j$,以及$i$*$j$有关,那么就可以斜率优化.

大致思路

你把式子暴力展开,然后把只跟$j$有关,跟$j$无关,跟$j$和$i$有关的分成三类,然后转移就好了.

考虑对于$j$>$k$,j为更优的决策,那么显然有:
$dp_j+val(i,j)<dp_k+val(i,j)$
这个东西把跟$i$有关的放到右边,剩下的在左边就可以了.
具体的还是看具体的题目吧.

[HNOI2008]玩具装箱toy

很容易写出$O(n^2)$的转移方程:
$dp_i=min(dp_j+(i-j-1+s[i]-s[j]-L)^2)$
接着看这个和斜率优化的适用范围很符合,于是就搞一个斜率优化套上去!
与$j$无关的有:$i^2,1,{s_i}^2,L^2,-2i,2is_i,-2iL,-2s_i,2L,-2s_iL$
只与$j$有关的有:$j^2$,${s_j}^2$,$2j,2js_j,2jL,2s_j,2s_jL$
与$i$和$j$有关的是:$-2ij,-2is_j,-2js_i,-2s_is_j$
考虑把最后一个式子变成$i$和$j$不相关:
$2ij+2is_j+2js_i+2s_is_j=2*(s_i+i)*(s_j+j)$
我们接下来就可以设
$y_i$为$i^2,1,{s_i}^2,L^2,-2i,2is_i,-2iL,-2s_i,2L,-2s_iL$的和.
$x_i=s_i+i$
考虑存在$j$>$k$且$j$是更优的转移点:
写一下$j$和$k$的转移式,然后与$i$无关的就是斜率了.
然后拿个单调队列随便搞一下就可以了.

代码戳这里

p.s.

在询问神仙$yyb$后才明白什么时候维护上凸壳/下凸壳.
你考虑你每一次的$k,就是$i$和$j$有关的那一堆化出来的只和$i$有关的东西他的递增关系.
如果是递减的,也就是斜率递减,那么就是上凸壳.
否则就是下凸壳,然后按照情况维护就好了.

[APIO2010]特别行动队

还是和上面那道题目一样,考虑那么三个东西:
与$j$无关:$a{s_i}^2,bs_i,c$
只与$j$有关:$a{s_j}^2,-bs_j$
与$i$和$j$有关:$-2as_is_j$

然后算出来斜率的式子应该是:
$((dp[i]+y[i])-(dp[j]+y[j]))/(s[i]-s[j])$
emmm,然后就按照上面的那个套路维护就好了.
这里维护的应该是一个上凸壳,具体看ps里面讲的.

代码戳这里

未完待续....