题目链接
https://www.luogu.org/problem/P3195
题解
斜率优化基础题。
设 \(s_i\) 为 \(c_i\) 的前缀和，\(f_i\) 为前 \(i\) 个物品的最小代价，不难推出这样的状态转移方程：
$$f_i=\min_{1 \leq j < i}{f_j+(s_j-s_i+i-j-1+L)^2}$$
然而这样转移的复杂度是 \(O(n^2)\) 的，在 \(n=50000\) 的数据面前还是需要优化。
首先让我们整理一下式子，令 \(A_i=s_i+i\)，\(B_i=s_j+j+1+L\)，则原转移方程可以化简成这样的形式：
$$f_i=\min_{1 \leq j < i}{f_j+(A_i-B_j)^2}$$
假如在 \(i\) 处存在两个决策点 \(x,y\)，满足 \(x>y\) 时，且 \(x\) 处的决策比 \(y\) 处更优。
我们可以写出一个不等式：
$$f_x+(A_i-B_x)^2<f_y+(A_i-B_y)^2$$
$$f_x+A_i^2+B_x^2-2A_iB_x<f_y+A_i^2+B_y^2-2A_iB_y$$
$$\frac{f_x+B_x^2-f_y-B_y^2}{B_x-B_y}<2A_i$$
左边式子的物理含义是比较明显的，它代表了一个一次函数的斜率，斜率优化的名称就由此而来。
我们接下来结合线性规划的知识来理解斜率优化。
假如目标函数（也就是直线）的斜率为 \(k\)，我们可以证明，当决策点左边的直线斜率均小于 \(k\)，右边直线斜率的直线均大于 \(k\) 时，该决策点是最优的决策点。在平面直角坐标系里表示的话，当目标直线与凸壳在上面所述的决策点处相切的时候，直线在 \(y\) 轴上的截距最小，即目标函数取得最小值。
现在算法的思路就清晰了，我们用单调队列来维护一个斜率递增的下凸壳，在每个状态 \(i\) 执行如下过程：
- 如果队首两点对应的直线斜率小于 \(2A_i\)，根据上文所述，该直线就变得无用了，我们将队首弹出队列。
- 我们找到的第一条斜率大于 \( 2A_i \) 的直线的左端点将会成为该状态的最优决策。（经过第 \(1\) 步的处理后，最优决策点一定会在队首）
- 我们接下来把当前状态 \(i\) 加入下凸壳中。注意到新加入的点可能会破坏凸壳斜率递增的性质，因此我们要检查队尾两点对应的直线斜率，如果不满足斜率递增性质，就将队尾出队，直到满足斜率递增或队列为空再将当前点 \(i\) 加入队列当中。
因为每个状态最多入队一次，出队一次，算法的复杂度是 \(O(n)\) 的。
做完 诗人小G 之后，你会发现，本题事实上是那道题目的特例。
当代价的幂次从 \(2\) 扩展到任意整数时，斜率优化便不再适合了，但我们可以通过证明决策单调性来解决这个更一般性的问题。
#include <iostream>
using namespace std;
long long s[50005],q[50005],f[50005],l,r,n,len;
long long a(int x)
{
return s[x]+x;
}
long long b(int x)
{
return s[x]+x+1+len;
}
double slope(int x,int y)
{
long long bx=b(x),by=b(y);
return double(f[x]+bx*bx-f[y]-by*by)/(bx-by);
}
int main()
{
cin>>n>>len;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
s[i]=s[i-1]+x;
}
for(int i=1;i<=n;i++)
{
while(l<r&&slope(q[l+1],q[l])<=2*a(i))
l++;
f[i]=f[q[l]]+(a(i)-b(q[l]))*(a(i)-b(q[l]));
while(l<r&&slope(q[r],q[r-1])>slope(i,q[r]))
r--;
q[++r]=i;
}
cout<<f[n]<<endl;
return 0;
}