题解 P2365 【任务安排】

· · 题解

其他题解里面的斜率优化讲的对新手不友好，我详细说一下吧

欢迎到博客食用喵~

先考虑O(N^2)的做法

因为分的批数是不定的，所有我们为了避免算后面的时候要用到前面分了多少批这个状态，我们采用费用提前的思想，在处理前面时把S产生的费用给计算了。

方程:f[i]代表前i个任务分成若干批产生的最小费用

转移:f[i]=min_{i=0}^{i-1}(f[j]+t[i]*(c[i]-c[j])+S*(c[n]-c[j])) 其中,t,c分别是任务时间和费用的前缀和的数组

考虑将状态转移方程化简：

f[j]=(S+t[i])*c[j]+f[i]-t[i]*c[i]-S*c[n]

注意：我们这里把min去掉了，是把j的取值集合所映射的f[j]和c[j]分别作为函数的f(x)和x

那么这个一次函数的斜率k就等于(S+t[i])，而截距b等于f[i]-t[i]*c[i]-S*c[n]

我们想让这个f[i]最小，那么其实就等价于b最小，在坐标系中，如果我们拿一个已知斜率的直线向上滑动，当它第一次碰见取值集合内的点(c[j],f[j])时，就取到了它的最小值

1.考虑什么时候一个点可以取到最小值

通过手玩我们发现（对于这个手玩真的是最好的理解方式了）

对于点J_2，当以x为关键字排序后的两个相邻的点J_1和J_3（在此题中对应c[j]的单调性）

当斜率k_1<k_0<k_2时，此点就是最优转移点

2.考虑什么时候一个点可能可以取到最小值，什么时候一定不能

如下图，当斜率k_1<k_2时，J_2是有机会的，此时三个点下凸

当斜率k_1>=k_2时，J_2不会有一点机会，此时三个点上凸

此时我们就可以用单调队列维护一个点集了，其中相邻点的斜率k必定是递增的

当需要做出决策的时候，我们二分这个点集，找到最优转移点。

针对于此题，我们发现每个决策点的斜率S+t[i]是单调递增的，那么我们可以直接维护队首，保证每次从队首转移。即当当前斜率大于队首与第二个点之间的斜率时，就出队。

统计完答案后再用二元组(f[i],c[i])更新队尾的元素，然后将它放进去

Code：

#include <cstdio>
#include <cstring>
const int N=5010;
int f[N],t[N],c[N],n,S,q[N],l,r;
int main()
{
    scanf("%d%d",&n,&S);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",t+i,c+i);
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    l=1,r=1;//注意此时已经把0作为元素放入了q[1]中去了
    for(int i=1;i<=n;i++)
    {
        while(l<r&&f[q[l+1]]-f[q[l]]<=(S+t[i])*(c[q[l+1]]-c[q[l]])) l++;
        f[i]=f[q[l]]+t[i]*c[i]+S*c[n]-c[q[l]]*(S+t[i]);
        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("%d\n",f[n]);
    return 0;
}