CF311B Cats Transport

题解 动态规划 动态规划-斜率优化DP 省选/NOI-
题目链接 编辑文章

题意

农场主养了 $M$ 只猫,它们会到 $N$ 座山上去玩,在 $T_i$ 的时候下山。农场主雇了 $P$ 个员工,员工可以在不同的时刻从第 $1$ 座山出发去接猫。求所有猫等待时间和的最小值。

$N,M\le 10^5 \ , \ P\le 100$ 。

题解

用 $t_i$ 表示接第 $i$ 只猫的最早出发时间,显然 $t_i = T_i - D_{H_i}$ ,然后将所有猫按照 $t_i$ 排序。

用 $f[i][j]$ 表示当前第 $i$ 个员工接走前 $j$ 只猫的最少等待时间。枚举上一次接走的猫 $k$ ,那么当前需要接走 $[k+1,j]$ 的猫。

显然刚好接走第 $j$ 只猫是最优的情况,方程式为:

$$f[i][j] = \min_{k=0}^{j-1} ( f[i-1][k] + \sum_{p=k+1}^j (t_i-t_p))$$

令 $S_i = \sum_{j=1}^i t_j$:

$$f[i][j] = \min_{k=0}^{j-1} ( f[i-1][k] + (j-k)\times t_j - S_j + S_k)$$

出现乘积,考虑斜率优化,将与 $k$ 有关的式子挪到左边:

$$S_k + f[i-1][k] = t_j\times k + (f[i][j] + S_j + j\times t_j)$$

斜率 $t_j$ 显然单调。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,p,d[100005],t[100005],s[100005],q[100005],f[105][100005];

signed main()
{
    n=read(); m=read(); p=read();
    for (ll i=2;i<=n;i++) d[i]=d[i-1]+read();
    for (ll i=1;i<=m;i++)
    {
        ll dis=d[read()];
        t[i]=read()-dis;
    }
    sort(t+1,t+m+1);
    for (ll i=1;i<=m;i++) s[i]=s[i-1]+t[i];
    for (ll i=1;i<=m;i++) f[1][i]=i*t[i]-s[i];
    ll ans=f[1][m];
    for (ll i=2;i<=p;i++)
    {
        ll l=1,r=1; q[l]=0;
        for (ll j=1;j<=m;j++)
        {
            while (l<r && s[q[l+1]]+f[i-1][q[l+1]]-s[q[l]]-f[i-1][q[l]]
                   <=(q[l+1]-q[l])*t[j]) l++;
            f[i][j]=f[i-1][q[l]]+(j-q[l])*t[j]-s[j]+s[q[l]];
            while (l<r && (s[q[r]]+f[i-1][q[r]]-s[q[r-1]]-f[i-1][q[r-1]])*(j-q[r])
                   >=(s[j]+f[i-1][j]-s[q[r]]-f[i-1][q[r]])*(q[r]-q[r-1])) r--;
            q[++r]=j;
        }
        ans=min(ans,f[i][m]);
    }
    return !printf("%lld",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。