P6302 回家路线

· · 题解

题意

给定 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;
}