题解 P2365 【任务安排】

算法:斜率优化动态规划

由于题解里没有关于的斜率优化做法,我打算写一下这种特殊的斜率优化动态规划

由于可以小于零,所以斜率不具有单调性,所以我们不能像原来一样维护下凸壳。我们不能只保留相邻两点斜率大于的部分,我们要把整个下凸壳都保留下来。这时队首也就不是最优解了，要二分找到一个左边比小,右边比大的位置。这个位置就是答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;
int l,r,n,s,t,c,j,sumt[N],sumc[N],f[N],q[N];
int find(int k)//二分查找左边比$s+sumt[i]$小,右边比$s+sumt[i]$大的位置
{
    if(l==r)return q[l];
    int L=l,R=r;
    while(L<R)
    {
        int mid=(L+R)/2;
        if(f[q[mid+1]]-f[q[mid]]<=k*(sumc[q[mid+1]]-sumc[q[mid]]))L=mid+1;
        else R=mid;
    }
    return q[L];
}
signed main()
{
    scanf("%lld%lld",&n,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&t,&c);
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    l=r=1;q[1]=0;
    for(int i=1;i<=n;i++)
    {
        int j=find(s+sumt[i]);//二分查找答案
        f[i]=f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]);
        while(l<r&&(f[q[r]]-f[q[r-1]])*(sumc[i]-sumc[q[r]])>=
        (f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]]))r--;//如果不构成下凸壳,就删除队尾
        q[++r]=i;
    }
    cout<<f[n]<<endl;
}