题解：P10450 & 斜率优化dp学习笔记

· · 算法·理论

本题有十分简单的做法，但可以作为斜率优化 Dp 的很好练手题。

斜率优化

在一些 dp 转移方程简化后，可以转换为坐标系中的一个斜率表示。

dp 的转移方程模型 dp_i = \min_j a_i x_j +y_j + M_i。

最大值和最小值优化方式相反。

然而 M_i 是一个对于 i 的常数，所以可以提到 \max 的外面。

我们发现 a_i 也是一个对于 i 的常数，把它当作斜率 k。

暂且忽略 M_i。

转换成 dp_i = \min_j k x_j +y_j 。

对于一条一次函数 y=kx+b。我们发现实际上 dp_i 就是函数中的 b。

也就是说已知斜率，求一些过点 (x,y) 斜率为 k 的函数，与 Y 轴相切的纵坐标（可以理解为一次函数 y=kx+b 中 b 的 最小 值）。

看下面的图，首先例如这三个点，红蓝绿。

我们发现在这个斜率下，红与 Y 轴相切的坐标最低，所以答案是红。

在看这个图，在这样的斜率下，绿与 Y 轴相切的坐标最低，所以答案是绿。

再看最后一个图，斜率更大时，绿与 Y 轴相切的坐标最低，答案依然是绿。

从而得出，无论怎样的斜率下，蓝必定都不是最优解。

所以可以忽略蓝这种情况。

而维护这样的点就与凸包有关。

凸包指的是一个坐标系中一些点，然后用一条边来“包”住他们。会变成一个凸多边形。例如下图，实线是 不合法 的情况，直观来看，他就是一个多边形的边“凹”了进去。所以此时需要把实线改成虚线。

而这些点，是我们之前 dp 已经计算出来的点，那么就可以维护进一个数据结构里。例如 HDU-3507 是一道典型的斜率优化 dp 题目。这道题中，我们可以保证斜率 大于 0。这样的情况就可以使用单调队列来维护。不满足这样的情况就可以在单调栈里使用二分来判断是上图所示的“红色”或“绿色”，因为满足单调性。

那么。

回看上面典型的式子改成取 \max，dp_i = \max_j a_i x_j +y_j + M_i。这时候相反，要维护一个上凸包。

一般来说，会根据式子的意义和手动画图，来推断较优解的方向，来判断上凸壳或者下凸壳。

然而通过上述规则，维护了多个点的下凸包就如下图（来自 oiwiki）。

本题

易得转移方程 dp_{j} = \max_{1 \leqslant i \leqslant j+1-L} \dfrac{s_j-s_k}{j-k}。其中 s_i = \sum_{j=1}^i a_j。

这种斜率方程与典型的有一点点区别，通过观察，易得：若 P(x,y) 表示一个坐标上的点，那么我们可以看做两个点 P_1(s_j,j) 和 P_2(s_k,k)。而 \dfrac{s_j-s_k}{j-k} 便是过这两点的直线的斜率。

题意转换：求其中两点之间的斜率最大值，并且两点之间的横坐标差值有限制。

于是考虑斜率优化 dp 转移。由于 0 \leqslant a_i，所以 s 作为前缀和必然是单调不递减的。所以可以用单调队列来维护。

还有，本题有精度问题，最好是在 s 在做前缀和的时候就乘上 1000。如果在最后再乘，会有精度问题然后导致 WA。

代码

int n,k;
int a[N];
double s[N];
int q[N],h,t;
double sol(int x,int y){
    return (s[x]-s[y])/(x-y);
}
void solve( ){
    cin >> n >> k;
    For(i,1,n) cin >> a[i];
    For(i,1,n) s[i] = s[i-1] + a[i];
    For(i,1,n) s[i] *= 1000;
    h = 1;
    double ans = 0;
    For(i,k,n){
        while(t>=h && sol(i,q[h]) <= sol(i,q[h+1]))++ h;
        ans = max(ans,sol(i,q[h]));
        while(t>=h && sol(q[t],q[t-1]) >= sol(i-k+1,q[t])) --t;
        q[++t] = i-k+1;
    }cout <<(int)ans;

}