P2365斜率优化学习笔记

· · 题解

题外话

今天开始学斜率优化了，以前看过但是看不懂被劝退了。省选马上要到了，还是得逼着自己学下去，要不然只能爆零了。
配合博客食用

题目描述

从零时刻开始，这些任务被分批加工，第$i$个任务单独完成所需的时间为$t_i$ 。在每批任务开始前，机器需要启动时间$s$，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。 每个任务的费用是它的完成时刻乘以一个费用系数$f_i$ 。请确定一个分组方案，使得总费用最小。 ### 初步分析 首先这个题我读了好几遍才读懂...... 你可能会问：不分批不是最好的吗，因为这样就只有一次机器启动时间啊。但是你忽略了一个问题，**每个任务的完成时间规定为他所在批次的最后一个任务完成的时间**，所以分一批不一定最优。 解决了这个问题之后，动态规划转移方程可以尝试写出来。 维护前缀和数组$sumt[\ ]$和$sumf[\ ]$，分别表示$t[\ ]$和$f[\ ]$的前缀和。 设$dp[i,j]$表示**把前$i$个任务分成$j$批**的最小费用。 那么很明显，第$j$批任务的完成时间就是第$j$批中最后一个任务（即$i$）在不分批情况下结束的时间（即$sumt[i]$）加上前面任务需要的开机时间（即$s\times j$）。 于是经典套路： $$dp[i,j]=\min\limits_{0\leq k< i}\{dp[k,j-1]+(s\times j+sumt[i])\times(sumf[i]-sumf[k])\}$$ 但是这个算法的时间复杂度为$\mathcal O(n^3)$，需要优化。 ### 费用提前计算优化 根据以往的做题经验，我们尝试把二维化成一维，即让$dp[i]$表示前$i$个任务分批执行的最小费用。 但是这样我们就不知道机器启动过几次了！ 别慌，冷静分析一下你会发现，如果我们要从$dp[j]$转移到$dp[i]$的话，由于第$j+1\sim i$都是在同一批内完成的，我们只需要把$s$对$j+1$后的影响补充到费用中就可以了！ $$dp[i]=\min\limits_{0\leq k<i}\{dp[j]+sumt[i]\times(sumf[i]-sumf[j])+s\times (sumf[n]-sumf[j])\}$$ 时间复杂度$\mathcal O(n^2)

这就是费用提前计算的思想。

斜率优化分析

他来了。
我们观察费用提前计算优化的式子：

dp[i]=\min\limits_{0\leq k<i}\{dp[j]+sumt[i]\times(sumf[i]-sumf[j])+s\times (sumf[n]-sumf[j])\}

有三个变量：j,dp[j],dp[i]。
我们把\min去掉，化简一下得到：

dp[j]=(s+sumt[i])\times sumf[j]+dp[i]-sumt[i]\times sumf[i]-s\times sumf[n]

这是个dp[j]关于sumf[j]一次函数，还带有其他变量。
那么斜率就是(s+sumt[i])，截距是dp[i]-sumt[i]\times sumf[i]-s\times sumf[n]。
我们最终的目的是找到f[i]的最小值，其实就是找截距的最小值。
接下来是重头戏！请一定要和我一起在纸上模拟！
我们在坐标系内画出f[j]与sumf[j]的散点图，用一条斜率为固定正整数的直线自下而上进行平移，第一次接触到一个点的时候就得到了最小截距。
现在我们就需要考虑，对于j_1<j_2<j_3，使j_2成为最优决策的条件。
我们发现j_2在j_1,j_3之间，无非就是两个位置：在j_1,j_3两点连线上方和下方。
如果将j_1j_2,j_2j_3连起来，形象地我们称第一种情况为上凸，第二种情况为下凸。
如果是上凸的话，我们发现，j_2永远不可能成为最优决策，因为要么先碰到j_1，要么先碰到j_3，永远碰不到j_2。
如果是下凸的话，j_2就有可能成为最优决策。
我们知道对于f(x)，连接(x_1,f(x_1))和(x_2,f(x_2))直线的斜率就是\frac{f(x_2)-f(x_1)}{x_2-x_1}，俗称“纵减纵除以横减横”。
所以j_2有可能成为最优决策的条件就是：

\frac{dp[j_2]-dp[j_1]}{sumf[j_2]-sumf[j_1]}<\frac{dp[j_3]-dp[j_2]}{sumf[j_3]-sumf[j_2]}

也就是说我们要维护一个斜率单调递增的下凸壳。
由于0\leq j<i，当i增加时，就会有新的决策，如果我们只保留连接相邻两点斜率大于s+sumt[i]的部分，那么最左端的就是最优决策。

斜率优化具体操作

建立一个单调队列q。
对于每个状态变量i：

  1. 检查队头q[l]与q[l+1]，如果\frac{dp[q[l+1]]-dp[q[l]]}{sumf[q[l+1]]-sumf[q[l]]}\leq s+sumt[i]，将q[l]出队，继续检查新队头。
  2. 取队头j=q[l]为最优决策，计算dp[i]。
  3. 把i插入队尾，在插入之前，若决策点j_1=q[r-1],j_2=q[r],j_3=i不满足斜率单调递增，则把q[r]出队，继续检查新队尾。

这样时间复杂度就变成了\mathcal O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
const int size=1e6+9;
int n,s;
int sumt[size],sumf[size],dp[size];
int l=1,r=1,q[size];
int main(){
    ios::sync_with_stdio(0);
    memset(dp,0x3f,sizeof(dp));
    cin>>n>>s;
    for(int i=1;i<=n;++i){
        int t,f;
        cin>>t>>f;
        sumt[i]=sumt[i-1]+t;
        sumf[i]=sumf[i-1]+f;
    }
    dp[0]=q[1]=0;
    for(int i=1;i<=n;++i){
        while(l<r&&dp[q[l+1]]-dp[q[l]]<=(s+sumt[i])*(sumf[q[l+1]]-sumf[q[l]])) l++;
        dp[i]=dp[q[l]]-(s+sumt[i])*sumf[q[l]]+sumt[i]*sumf[i]+s*sumf[n];
        while(l<r&&(dp[q[r]]-dp[q[r-1]])*(sumf[i]-sumf[q[r]])>=(dp[i]-dp[q[r]])*(sumf[q[r]]-sumf[q[r-1]])) r--;
        q[++r]=i;
    }
    cout<<dp[n]<<endl;
    return 0;
}