Cats Transport 详细讲解
题目跳转:CF311B Cats Transport
题目大意
有 \(m\) 只猫,\(p\) 个饲养员,\(n\) 座山。第 \(i-1\sim i\) 座山之间的距离为 \(d_i\)。第 \(i\) 只猫去 \(h_i\) 号山玩,玩到 \(t_i\) 时刻停止,然后开始等待饲养员。请规划每个饲养员从 \(1\) 号山出发的时间,使得所有猫的等待时间总和最小。
题意转化
每个饲养员都从山丘 \(1\) 出发,速度为 \(1\)。设 \(dis_i\) 表示山丘 \(1\) 到山丘 \(i\) 的距离。
对于第 \(x\) 只猫,它在山丘 \(h_x\) 等待,结束时间为 \(t_x\)。如果饲养员从山丘 \(1\) 出发的时间为 \(T\),那么它到达山丘 \(h_x\) 的时间为:
能接到这只猫当且仅当:
也就是:
我们设 \(a_x=t_x-dis_{h_x}\),则饲养员出发时间 \(T\) 能接到第 \(x\) 只猫,当且仅当 \(T\geq a_x\)。接到它时,猫的等待时间为:
于是问题变成了:
有 \(m\) 个数 \(a_1,a_2,\dots,a_m\)。需要安排至多 \(p\) 个出发时间,每个出发时间 \(T\) 会接走所有满足 \(a_i\le T\) 的猫,代价为 \(\sum (T-a_i)\)。求最小总代价。
思路分析
提前处理
将 \(a_i\) 从小到大排序。现在考虑:如果两个饲养员分别接走的猫在排序后发生交叉,那么交换它们负责的猫不会使答案更劣。
因此在排序后,最优方案中每个饲养员负责的猫一定是一段连续的区间。
设 \(sum_i=\sum_{j=1}^{i} a_j\),如果某个饲养员负责接走区间 \(j+1\sim i\) 内的猫,那么出发时间取 \(T=a_i\) 时一定最优(因为必须能接到区间内最晚的猫,而出发越早,等待时间越短)。
则这一段猫的总等待时间就是:
DP 设计与状态转移
我们设 \(dp_{i,j}\) 表示前 \(i\) 个饲养员接走排序后前 \(j\) 只猫的最小总等待时间。
显然可得状态转移方程:
化简整理(把与 \(k\) 有关和与 \(k\) 无关的分开):
由于 \(a_i\) 已经排序,是单调不降的,因此可以使用斜率优化快速求出答案。
斜率优化
稍加整理
先把状态转移方程去掉 \(min\):
移项:
设
那么状态转移方程就变为了一个一次函数:
对于每个 \(k\),看做一个在平面直角坐标系的决策点 \((k,dp_{i-1,k}+sum_k)\)。
比较两个决策 \(u\lt v\),决策 \(v\) 比决策 \(u\) 更优,当且仅当:
也就是:
因此可以用单调队列维护一个下凸壳。
队首弹出
若队列中有两个决策 \(u\leq v\),且:
说明 \(v\) 比 \(u\) 更优,弹出 \(u\)。
代码中对应:
bool check2(ll x,ll y,ll z,ll i){
return (i128)(gy(y,i)-gy(x,i))<=(i128)a[z]*(y-x);
}
其中 \(z\) 对应当前的 \(i\)。
队尾维护凸壳
对于三个决策 \(u\lt v\lt w\),如果:
则 \(v\) 不可能成为最优决策,可以从凸壳中删除。
交叉相乘并整理,可写成:
代码中对应:
bool check1(ll x,ll y,ll z,ll i){
return (i128)(gy(y,i)-gy(x,i))*(z-x)>=(i128)(gy(z,i)-gy(x,i))*(y-x);
}
初始化
当只有一个饲养员时,他需要接走前 \(i\) 只猫,最优出发时间是 \(a_i\),等待时间为:
最终答案可以少于等于 \(p\) 个饲养员,因此初始:
ans=dp[1][m];
之后每计算一层 \(i\),更新:
ans=min(ans,dp[i][m]);
注意点
斜率优化交叉相乘时,乘积可能达到 \(10^{19}\) 级别,超过 long long 的范围,必须使用 __int128。
时间复杂度分析
对于每次循环,每个 \(j\) 只入队一次,也只出队一次,是 \(O(m)\) 的;再加上外面一层循环,总时间复杂度是 \(O(pm)\) 的,可以完美通过此题。
代码
#include
using namespace std;
typedef long long ll;
typedef __int128 i128;
uint8_t buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
ll rd(){
ll x=0,f=1,ch=gc();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=gc();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=gc();
}
return x*f;
}
void write(ll x){
if(x<0){
x=-x;
putchar('-');
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
const ll maxn=1e5+5,maxp=1e2+5;
ll n,m,p,dis[maxn],h,t,l,r,a[maxn],sum[maxn],dp[maxp][maxn],q[maxn],ans;
ll gy(ll x,ll i){
return dp[i-1][x]+sum[x];
}
bool check1(ll x,ll y,ll z,ll i){
return (i128)(gy(y,i)-gy(x,i))*(z-x)>=(i128)(gy(z,i)-gy(x,i))*(y-x);
}
bool check2(ll x,ll y,ll z,ll i){
return (i128)gy(y,i)-gy(x,i)<=(i128)a[z]*(y-x);
}
int main(){
n=rd();
m=rd();
p=rd();
for(ll i=2;i<=n;i++){
dis[i]=rd()+dis[i-1];
}
for(ll i=1;i<=m;i++){
h=rd();
t=rd();
a[i]=t-dis[h];
}
sort(a+1,a+m+1);
for(ll i=1;i<=m;i++){
sum[i]=sum[i-1]+a[i];
dp[1][i]=i*a[i]-sum[i];
}
ans=dp[1][m];
for(ll i=2;i<=p;i++){
l=1;
r=0;
for(ll j=1;j<=m;j++){
while(ldp[i][m]){
ans=dp[i][m];
}
}
write(ans);
return 0;
}
如果您觉得有不正确或不妥的地方,欢迎在评论区指正,感谢!
如果觉得对你有帮助,就帮忙点个赞吧!(❁´◡`❁)
原文地址: https://www.cveoy.top/t/topic/qHYk 著作权归作者所有。请勿转载和采集!