自动搬运

查看原文

来自洛谷，原作者为

	Mentos_Cola .

搬运于2025-08-24 22:19:29，当前版本为作者最后更新于2020-08-13 21:09:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定 $n$ 个点，从 $1$ 走到 $n$ ；其中有 $m$ 条路径，第 $i$ 条路径从 $x_i$ 到 $y_i$ ，时间从 $p_i$ 到 $q_i$ ，每次等车 $t$ 的时间会增加 $A*t^2+B*t+C$ 的花费，最后花费加上一个到达时间。使花费最小。

Solution

一开始我想以当前所在地点为状态来 $DP$，但是这样就需要再记一维时间，复杂度爆表。于是我们把这些路径作为状态进行转移，就能够同时记下地点和时间了。

那么设 $dp[i]$ 为走 $i$ 路径前的总花费，套路地进行 $DP$ 转移方程的斜率优化：

$ dp[i]=dp[j]+A\times(p_i-q_j)^2+B\times(p_i-q_j)+C $

$dp[i]=dp[j]+Ap_i^2+Aq_j^2-2Ap_iq_j+Bp_i-Bq_j+C$

$dp[j]+Aq_j^2-Bq_j=2Ap_iq_j+dp[i]-Ap_i^2-Bp_i-C$

至此我们以

$ y=dp[j]+Aq_j^2-Bq_j,k=2Ap_i,x=q_j,b=dp[i]-Ap_i^2-Bp_i^2-C $

把 $m$ 条路径按照 $p$ 从小到大处理，$k$单调不减，即可进行斜率优化 $DP$

但是我们还有两个限制，一个是 $y_j=x_i$ ，另一个是 $q_j\le p_i$

第一个好办，我们开 $n$ 个 单调队列，$i$ 进队时就丢进第 $y_i$ 个单调队列里，求 $dp[i]$ 时就从第 $x_i$ 个单调队列里调就完了。

第二个则需要我们算出 $dp[i]$ 后不将它马上插到对应的单调队列里，而是按照 $q$ 把它丢到桶里。对每个 $d$ 算所有 $p_i=d$ 的 $dp[i]$ 之前，就把所有 $q_j=d$ 的 $j$ 插入对应单调队列。

这样为什么可行呢？在算 $dp[i]$ 时，桶里所有 $q_j\le p_i$ 都会进入单调队列中。而所有 $q_j\le p_i$ 的 $j$ 必然 $p_j<p_i$ ，它们一定在之前就会进入桶中。这样，我们就证明了我们不会漏掉任何可能的转移。

我看到上面的题解大多都使用了堆，带上了一个 $log$ 的时间复杂度。但实际上此题数据范围不大，用桶排更简洁，也更快。

代码：

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int M=1e6+10,inf=1e18,eps=1e-9;
int st[M],nd[M],p[M],q[M],x[M],y[M],h[M],t[M],dp[M];
vector<int>pos[M],ins[M],Q[M];
void read(int &x){
	int f=1;x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
int pf(int x){return x*x;}
double slope(int i,int j){
	int xx=x[j]-x[i],yy=y[j]-y[i];
	if(!xx){
		if(yy>0)return inf;
		return -inf;
	}
	return yy*1./xx;
}
signed main(){
	int n,m,A,B,C,T=0,ans=inf;
	read(n),read(m),read(A),read(B),read(C);
	for(int i=1;i<=m;i++){
		read(st[i]),read(nd[i]),read(p[i]),read(q[i]);
		T=max(T,q[i]),pos[p[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)h[i]=0,t[i]=-1;
	for(int pi=0;pi<=T;pi++){
		for(int id=0;id<ins[pi].size();id++){
			int i=ins[pi][id],pp=nd[i];
			while(h[pp]<t[pp]&&slope(Q[pp][t[pp]-1],Q[pp][t[pp]])>=slope(Q[pp][t[pp]-1],i))t[pp]--;
			++t[pp];
			if(t[pp]>=Q[pp].size())Q[pp].push_back(i);
			else Q[pp][t[pp]]=i;
		}
		for(int id=0;id<pos[pi].size();id++){
			int i=pos[pi][id],pp=st[i];double k=2.*A*pi;
			while(h[pp]<t[pp]&&slope(Q[pp][h[pp]],Q[pp][h[pp]+1])<k)h[pp]++;
			if(h[pp]>t[pp]&&st[i]!=1)continue;
			int j;
			if(st[i]==1&&h[pp]>t[pp])j=0;
			else j=Q[pp][h[pp]];
			dp[i]=dp[j]+A*pf(p[i]-q[j])+B*(p[i]-q[j])+C;
			x[i]=q[i],y[i]=dp[i]+A*pf(q[i])-B*q[i];
			ins[q[i]].push_back(i);
			if(nd[i]==n)ans=min(ans,dp[i]+q[i]);
		}
	}
	cout<<ans<<endl;
	return 0;
}