$qwq$今天$rqy$给窝萌这些蒟蒻讲了斜率优化……大概是他掉打窝萌掉打累了吧顺便偷了$rqy$讲课用的图

$Step \ \ 1$ 一点小转化

事实上斜率优化是专门用来处理这样一类$dp$式子的 $$dp_i = A_i + \max \limits _{j = 1}^{i -1}(B_j - C_j \times base_i)$$窝萌尝试把上式中的$B_j$、$C_j$和$base_i$等价成$x_j$、$y_j$和$k_i$，并把它们丢到一个平面上,然后它萌就会变成一堆点$(x_j,y_j)$，画一条过他们的直线，类似于$$y - y_j = k_i(x - x_j)$$变换一下$$y = k_ix + (y_j + x_j)$$窝萌会发现，现在窝萌所求的不过是一条截距最大的直线而已。那么其实就是相当于求一个给定$k$意义下最靠上的点。

$qwq$那么窝萌不妨先减弱问题的不可做性，使其单调——令$x$单调增、$k_i$单调减。

那当窝萌在朴素$DP$遍历所有的$k_i$时，所得到的直线的轨迹应该是这样的:

（上图是个$GIF$……不动的话就拖出来看吧）轨迹正好是一个凸壳，并且你会发现它的轨迹正好是再绕着每个斜率下最优的点旋转。

$rqy$对此是这么解释的：

可以发现好多点是没有机会作为最优的点的。

形象⼀点的说，如果⼀个点的左边和右边某两个点在它上⽅“搭起”了⼀条线段，那么它就永远不会被选到。

而因为我们保证了$x$和$k$的单调性，所以就我们可以比较方便的考虑“如何选取当前最优点”这个问题。我们考虑遇到一个新的点，是否把他加入最优解集合里面，其实质就是维护一个上凸壳。那么已知两个点$A$和$B$，现在遇到了新加入的点$C$，此时有两种情况：

1、$BC$的斜率大于$AB$的斜率

这时我们需要抛弃$B$，直接连接$AC$：

2、$BC$的斜率小于$AB$的斜率

通过这种方式我们就可以完成对整个凸壳的维护。而在判定时也很简单，用叉积来判断即可，即有$A$、$B$、$C$三个点分别是$(x_A,y_A),(x_B,y_B),(x_C,y_C)$满足$x_A \leq x_B \leq x_C$，那么如果$$(x_C-x_A)(y_B - y_A) - (x_B - x_A)(y_C- y_A) < 0$$则证明是第一种情况，否则是第二种。

$emmmm$直接求斜率当然也是可以的吧，不过会不会很慢很麻烦啊$qwq$。

$Step \ \ 2$ 代码实现以及拓展

$emmm$我们考虑用一个逻辑上单调的队列来实现去掉不优的状态 +加入新的状态。回归上题，我们所求的是$max$，所以我们需要去掉那些斜率小的状态；同时需要加入斜率大的状态。由于整个过程牵扯到前后删点，所以用双端队列来维护。本蒟蒻的（伪）代码如下：

int queue[MAXN] ;

int head = 0, tail = 0 ;

for(i = 1; i <= N; i ++){

	while (1){

		A = queue[head], B = queue[head + 1] ;

		if (y[A] - k[i] * x[A] < y[B] - k[i] * x[B]) head ++ ;

		else break ;

	}

	dp[i] = base[i] + y[A] - k[i] * x[A] ;

	Maybe y[i] needs calcing ?

	Maybe x[i] also needs calcint ?

	So, Calc_it() ;

	while (tail - head >= 2){

		A = queue[tail - 1], B = queue[tail] ;

		if ((y[i] - y[A]) * (x[B] - x[A])

		  - (x[i] - x[A]) * (y[B] - y[A]) > 0)

		  	tail-- ;

		else break ;

	}

	queue[++ tail] = i ;

}

对了……我在啃这个地方时出了个$bug$……那是因为我一直以为$y$和$x$从本质上来讲有$n^2$个……$OTZ$

那么对于拓展而言，我们以上做的一切都是基于“$x$和$k$单调”这一前提的，那么还会有以下两种情况：

1、$x$不单调

那么实质上就是我们需要动态插入删除、从内部删除，那么就需要用平衡树来维护一个凸包了。

2、$k$不单调

那么实质上就是我们原来比较方便的第一个$while$——从左往右直接删是不行的了，因为现在不优不代表之后不优，所以此时我们需要的就是三分一个位置而不是从前向后扫、

哦，还有，对于$dp$式子而言，如果它长这个样子：$$dp_i = A_i + \min \limits _{j = 1}^{i -1}(B_j - C_j \times base_i)$$那么其实我们维护的就是一个下凸壳，所以此时只需要把所有的大于号改成小于号即可。

嗝……那么下面就来看题吧

#$\mathcal{\color{red}{Description}}$

$Link$

给定一个序列$C$和一个常数$P$ 。你要将序列划分成若干段；每一段如果从$L$到$R$、整段的和为$S$ ，则会产生$(R-L+S-P)^2$的代价，求最小代价。

#$\mathcal{\color{red}{Solution}}$

对于这个题而言，我们考虑先把这个恶心的式子化简一下：$$(R-L+S-P)^2 = (R -L + \sum \limits_{i=L}^{R}{C_i} +P)^2 = (\sum \limits_{i=L}^{R}{C_i + 1} - (P + 1)) ^ 2$$然后我们发现这玩意儿只要我们一开始把输入的所有$C_i$和$P++$就好了……但我并没有这么做$qwq$……因为这是$rqy$的做法$hhhhh$。

回归刚才的，我们观察原式其实可以得出不同的式子，比如我们把$(\sum \limits _{i=L}^{R}{C_i + 1} - (P + 1))^2$写成 $(S - L) ^ 2$，那么就是$$(sum_R - sum{L-1} + (R - L - 1)-P-1)^2$$而对于比较朴素的$dp$方程来讲，他大概长这样$$dp_i = min(dp_j + (sum_R - sum_{L} + (R - L)-P-1)^2)$$窝萌不妨记一个$A_i = sum_i + i,B_i = sum_i+i+P+1$，那么原来的方程就可以写作$$dp_i = min(dp_j + (A_i-B_j)^2)$$稍微展开一下就是$$dp_i = dp_j+A_i^2 + B_j^2 - 2A_iB_j$$然后你就会发现跟斜率优化的板子们惊人的相似……其中$A_i$ 只跟$i$ 有关，看作模型中的$A_i$ （常项），$dp_j+B_j^2$ 看作模型中的$B_j$ ，$B_j$看作模型中的$C_j$ ，$2A_i$ 看作模型中的$base_i$，即斜率$k$，跑一个斜率优化$DP$即可。

#include <cstdio>

#include <iostream>

#define MAXN 200010

using namespace std ; int T1, T2 ;

int N, L, head = 1, tail = 1, que[MAXN], i ;

double S[MAXN], A[MAXN], B[MAXN], dp[MAXN] ;

inline double qr(){

    int k = 0 ; char c = getchar() ;

    while (c < '0' || c > '9') c = getchar() ;

    while (c <= '9' && c >= '0') k = (k << 1) + (k << 3) + c - 48, c = getchar() ;

    return (double)k ;

}

inline double get_x(int now){return B[now] ;}

inline double get_y(int now){return dp[now] + B[now] * B[now] ;}

inline double get_K (double a, double b){

    return ( get_y(a) - get_y(b) )/ ( get_x(a) - get_x(b) ) ;

}

int main(){

    cin >> N >> L ;

    for (i = 1; i <= N; i ++) S[i] = qr() + S[i - 1] ;

    for (i = 0; i <= N; i ++) A[i] = S[i] + i, B[i] = A[i] + L + 1 ;

    for (i = 1; i <= N; i ++){

        while (head < tail && get_K(que[head], que[head + 1]) < 2 * A[i]) ++ head  ;

        dp[i] = dp[que[head]] + (A[i] - B[que[head]]) * (A[i] - B[que[head]]) ;

        while (head < tail && get_K(que[tail - 1], i) < get_K(que[tail], que[tail - 1])) -- tail  ;

        que[++ tail] = i ;

    }

    cout << ((long long)dp[N]);

}

```

巴特西

学习笔记·斜率优化 [HNOI2008]玩具装箱

\(Step \ \ 1\) 一点小转化

1、\(BC\)的斜率大于\(AB\)的斜率

2、\(BC\)的斜率小于\(AB\)的斜率

\(Step \ \ 2\) 代码实现以及拓展

#\(\mathcal{\color{red}{Description}}\)

#\(\mathcal{\color{red}{Solution}}\)

最新文章

热门文章