引入
有时候 我们会遇见一些 dp 式子
\[f_i=\min(f_j+a_i\times b_i)(j\leq i-1)
\]
这些式子和 \(j\) 没有任何关系 可以前缀处理最小值 \(O(n)\) 快速解决
但是有些式子是这样的
\[f_i=\min(f_j+a_i\times b_j+c_i)
\]
这种问题可以使用斜率优化至 \(O(n\log n)\)
例题
传送门
很容易看出来是 dp
多一维时间会非常麻烦 我们考虑费用预处理 就不用考虑启动时间了
总之 最后可以得到这个式子
\[f_i=f_j+t_i\times(c_i-c_j)+m\times (c_n-c_j)
\]
时间复杂度 \(O(n^2)\)
其中 \(t\space c\) 是题目数组给出的前缀和数组
看到这个式子 想要优化一定要大力拆
\[f_i=f_j+t_i\times c_i-t_i\times c_j+m\times c_n-m\times c_j
\]
难点就在于其中有 \(j\) 的项 观察可以发现它们的系数是固定的 这时候就是斜率优化了
把 \(f_j\) 扔到左边
\[f_j=f_i-t_i\times c_i+t_i\times c_j-m\times c_n+m\times c_j
\]
整理得
\[\underline{f_j}_{\space y}=\underline{c_j}_x\times \underline{(t_i+m)}_k+\underline{f_i-t_i\times c_i-m\times c_n}_b
\]
容易发现可以表示成一次函数的形式
这个一次函数的 \(k\) 是固定的
要 \(f_i\) 取到最小 就是让 \(b\) 取到最小
一个点对是 \((c_j,f_j)\)
数形结合 把点对拍上去
一条已知斜率的直线上 把这条直线往上移 碰到的第一个点取到函数最小值
那么 取到最小值的点有什么要求？
经过大量的手推归纳画图 可以得到一个点取到最小值的要求
只有当 \(k1< k0< k2\)时 这个点才能取到最小
然后会有很多点 有一些可能根本不会取到的点我们可以找到规律：
绿色的下凹包可以取到最小 红色的上凸包不可能取到最小
我们可以维护有效点 即保证任意两点的 \(k\) 值严格递增
因为这道题的 \(x\) 点保证递增 因此可以丢进队列里
然后 \(k\) 值也是递增的 可以直接使用单调队列维护
每次从队首更新即可
时间复杂度 \(O(n)\)
Code
int main()
{
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
l=r=1;//这里就是把f[0]=0 加进去 坐标 (0,0)
for(int i=1;i<=n;i++)
{
while(l<r&&(f[q[l+1]]-f[q[l]])<=(c[q[l+1]]-c[q[l]])*(t[i]+m)) ++l;//把小于的当前斜率的点删掉 得到第一个大于当前斜率的点的左边的点
f[i]=f[q[l]]+t[i]*c[i]-t[i]*c[q[l]]+m*c[n]-m*c[q[l]];
while(l<r&&(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])) --r;//维护斜率递增
q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}