题目链接
303. 运输小猫
小 $S$ 是农场主,他养了 $M$ 只猫,雇了 $P$ 位饲养员。
农场中有一条笔直的路,路边有 $N$ 座山,从 $1$ 到 $N$ 编号。
第 $i$ 座山与第 $i-1$ 座山之间的距离为 $D_i$。
饲养员都住在 $1$ 号山。
有一天,猫出去玩。
第 $i$ 只猫去 $H_i$ 号山玩,玩到时刻 $T_i$ 停止,然后在原地等饲养员来接。
饲养员们必须回收所有的猫。
每个饲养员沿着路从 $1$ 号山走到 $N$ 号山,把各座山上已经在等待的猫全部接走。
饲养员在路上行走需要时间,速度为 $1$ 米/单位时间。
饲养员在每座山上接猫的时间可以忽略,可以携带的猫的数量为无穷大。
例如有两座相距为 $1$ 的山,一只猫在 $2$ 号山玩,玩到时刻 $3$ 开始等待。
如果饲养员从 $1$ 号山在时刻 $2$ 或 $3$ 出发,那么他可以接到猫,猫的等待时间为 $0$ 或 $1$。
而如果他于时刻 $1$ 出发,那么他将于时刻 $2$ 经过 $2$ 号山,不能接到当时仍在玩的猫。
你的任务是规划每个饲养员从 $1$ 号山出发的时间,使得所有猫等待时间的总和尽量小。
饲养员出发的时间可以为负。
输入格式
第一行包含三个整数 $N,M,P$。
第二行包含 $n-1$ 个整数,$D_2,D_3,…,D_N$。
接下来 $M$ 行,每行包含两个整数 $H_i$ 和 $T_i$。
输出格式
输出一个整数,表示所有猫等待时间的总和的最小值。
数据范围
$2 \le N \le 10^5$,
$1 \le M \le 10^5$,
$1 \le P \le 100$,
$1 \le D_i < 1000$,
$1 \le H_i \le N$,
$0 \le T_i \le 10^9$
输入样例:
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
输出样例:
3
解题思路
斜率优化dp
假设某位饲养员的开始时刻为 $s$,对于某只猫来说,如果有 $s+d[i]\geq t[i]$,其中 $d[i]$ 表示第 $i$ 座山到第 $1$ 座的距离,说明该饲养员可以接走这只猫,且该猫的等待时间为 $s-(d[i]-t[i])$,设 $A[i]=d[i]-t[i]$,将所有的 $a[i]$ 排序,显然,$s$ 应该选择其中若干个 $a[i]$ 更优,有如下 dp
-
状态表示:$f[i][j]$ 表示 $i$ 个饲养员负责 $j$ 只猫的最少等待时间
-
状态计算:$f[i][j]=min\{f[i-1][k]+A[j]\times (j-k)-(sum[j]-sum[k])\}$,其中 $sum[i]$ 为 $A[i]$ 的前缀和
对上式进行转化,得 $f[i-1][k]+sum[k]=A[j]\times k+f[i][j]-A[j]\times j+sum[j]$,将 $f[i-1][k]+sum[k]$ 看作 $y$,$k$ 看作 $x$,$A[j]$ 看作直线的斜率,$f[i][j]-A[j]\times j+sum[j]$ 看作截距,与 $k$ 有关的都视为变量,其他为常量,显然 $-A[j]\times j+sum[j]$ 是一个常量,要使 $f[i][j]$ 最小,即截距最小,同时,这里的 $k$ 且直线的斜率也递增,即可转化为 301. 任务安排2 这题的解法
另外,需要注意:$f[i][j]$ 需要初始化为正无穷,初始化状态 $f[i][0]=0$ 表示 $0$ 只猫,无论有多少饲养员,其等待时间都为 $0$,而 $f[0][i]$ 需要置为正无穷,因为有 $i>0$ 只猫但是没有饲养员是非法状态,置为 $0$ 的话会影响后续状态的转移
- 时间复杂度:$O(n)$
代码
// Problem: 运输小猫
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/305/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e5+5;
int n,m,p,d[N];
int hh,tt,q[N];
LL f[105][N],a[N],s[N];
LL get_y(int k,int j)
{
return f[j-1][k]+s[k];
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=2;i<=n;i++)
{
scanf("%d",&d[i]);
d[i]+=d[i-1];
}
for(int i=1;i<=m;i++)
{
int x;
scanf("%d%lld",&x,&a[i]);
a[i]-=d[x];
}
sort(a+1,a+1+m);
for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
memset(f,0x3f,sizeof f);
for(int i=0;i<=p;i++)f[i][0]=0;
for(int i=1;i<=p;i++)
{
hh=tt=q[0]=0;
for(int j=1;j<=m;j++)
{
while(hh<tt&&get_y(q[hh+1],i)-get_y(q[hh],i)<=(q[hh+1]-q[hh])*a[j])hh++;
int k=q[hh];
f[i][j]=f[i-1][k]+s[k]-s[j]+a[j]*(j-k);
while(hh<tt&&(get_y(q[tt],i)-get_y(q[tt-1],i))*(j-q[tt])>=(get_y(j,i)-get_y(q[tt],i))*(q[tt]-q[tt-1]))tt--;
q[++tt]=j;
}
}
printf("%lld",f[p][m]);
return 0;
}