$CF311B Cats Transport$ 斜率优化

AcWing

Description

 

Sol

设f[i][j]表示前i个饲养员接走前j只猫咪的最小等待时间.

要接到j猫咪,饲养员的最早出发时间是可求的,设为d:

$ d[j]=Tj-sum_{k=1}^{Hi}Dk$

然后把d从小到大排序并且求出前缀和s.注意到,一个饲养员带走的猫咪一定是按d排序后连续的一段.假设一个饲养员最后一个接走的猫是第k只,他后面一个饲养员是在d[k]时间出发的,那么,他能接走[k+1,j]的所有猫咪.

$f[i][j]=min{f[i-1][k]+dj*(j-k)-(sj-sk)}$

把外层循环i看做定值,j是状态变量,k是决策点.方程中存在d_j*k,应该考虑斜率优化.去掉min函数,移项.

$ f[i-1][k]+sk=dj*k-f[i][j]-dj*j+sj $

k是单调递增的,f[i-1][k]+s_k也是单调递增的,所以就直接斜率优化辣

然后由于排过序d_j也是单调递增的,所以就和任务排序2一样辣

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i<=b;i++)
#define yes(i,a,b) for(Rg int i=a;i>=b;i++)
#define inf 1e18
#define int long long
using namespace std;
il int read()
{
    int x=0,y=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*y;
}
const int N=(1e5)+1;
int n,m,p,d[N],h[N],t[N],a[N],s[N],f[101][N],q[N];
main()
{
    n=read(),m=read(),p=read();
    go(i,2,n)d[i]=d[i-1]+read();
    go(i,1,m)h[i]=read(),t[i]=read();
    go(i,1,m)a[i]=t[i]-d[h[i]]-d[1],f[0][i]=inf;
    sort(a+1,a+m+1);
    go(i,1,m)s[i]=s[i-1]+a[i];
    go(i,1,p)
    {
        int l=1,r=1;
        go(j,1,m)
        {
            while(l<r && (f[i-1][q[l+1]]+s[q[l+1]]-f[i-1][q[l]]-s[q[l]]<=a[j]*(q[l+1]-q[l])))l++;
            f[i][j]=f[i-1][q[l]]+a[j]*(j-q[l])-(s[j]-s[q[l]]);
            while(l<r && 1LL*(f[i-1][j]+s[j]-f[i-1][q[r]]-s[q[r]])*(q[r]-q[r-1])<=1LL*(f[i-1][q[r]]+s[q[r]]-f[i-1][q[r-1]]-s[q[r-1]])*(j-q[r]))r--;
            q[++r]=j;
        }
    }
    printf("%lld
",f[p][m]);
    return 0;
}