P5468 [NOI2019]回家路线

传送门

看题目一眼斜率优化，然后写半天调不出来

结果错误的 $dfs$ 有 $95$ 分？暴力 $SPFA$ 就 $AC$ 了？

讲讲正解：

显然是斜率优化的式子：

先不考虑 $q_{s_k}$ 的贡献，设 $f[i]$ 表示当前时间为 $i$ 的最小代价

如果不考虑位置关系，有 $f[p_i]=f[q_j]+A(p_i-q_j)^2+B(p_i-q_j)+C$

拆开来：$f[p_i]=f[q_j]+Ap_i^2-2Ap_iq_j+Aq_j^2+Bp_i-Bq_j+C$

换一下位置 $2Ap_iq_j+f[p_i]-Ap_i^2-Bp_i-C=f[q_j]+Aq_j^2-Bq_j$

那么 $k=2Ap_i,x=q_j,b=f[p_i]-Ap_i^2-Bp_i-C,y=f[q_j]+Aq_j^2-Bq_j$

显然直接斜率优化

但是有位置和时间关系，不妨把每列车按时间拆成两点 $p,q$ 分别对应询问和插入，然后按时间拍好序

这样每列车出发时，时间在它之前到达的车都处理完了，可以直接计算贡献，在每列车到达时，再把新的贡献插入凸包

因为还有位置的限制关系，所以对每个位置开一个 $vector$ 维护对应位置的凸包

然后就是具体的实现细节了...

发现维护凸包时是从右边插入，左边弹出，插入可以直接用 $vector$ 的 $push\_back,pop\_back$

左边弹出可以对每个 $vector$ 维护一个变量 $pos$ 表示当前最左的合法点

对最终答案的更新可以在更新 $dp$ 数组时特判

然后就要注意各种细节问题了（调到吐血）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(x=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=4e5+,INF=2e9+;

int n,m,A,B,C,ans=INF,pos[N],val[N];//val维护每列火车的贡献

inline int calc(int t) { return A*t*t+B*t+C; }

struct Train{//列车

    int x,y,p,q;

}T[N];

struct dat{//按时间排序的点

    int tim,type,id;//type判断插入还是查询,id是火车编号

    inline bool operator < (const dat &tmp) const {

        return tim<tmp.tim;

    }

}D[N];

struct datt{//凸包的点

    int tim,res;//时间,已经产生的代价

    inline int X() { return tim; }

    inline int Y() { return res-A*tim*tim-B*tim; }

};

vector <datt> V[N];//vector维护凸包

inline ll Cross(ll xa,ll xb,ll ya,ll yb) { return xa*yb-xb*ya; }//叉积判断直线之间的关系

inline int Y(int p) { return val[p]-A*T[p].q*T[p].q-B*T[p].q; }

inline void push(int p)//插入

{

    int t=T[p].y; if(val[p]>=INF) return;//注意特判

    while(int(V[t].size())-pos[t]>=)//记得-pos[t]

    {

        int len=V[t].size();

        if( Cross( T[p].q-V[t][len-].X() , Y(p)-V[t][len-].Y() , V[t][len-].X()-V[t][len-].X() , V[t][len-].Y()-V[t][len-].Y() ) <  )

            break;

        V[t].pop_back();//vector自带函数

    }

    V[t].push_back((datt){T[p].q,val[p]});//加入

}

int main()

{

    //freopen("route.in","r",stdin);

    //freopen("route.out","w",stdout);

    n=read(),m=read(),A=read(),B=read(),C=read();

    int a,b,c,d,tot=;

    for(int i=;i<=m;i++)

    {

        a=read(),b=read(),c=read(),d=read();

        T[i]=(Train){a,b,c,d};

        D[++tot]=(dat){c,,i}; D[++tot]=(dat){d,,i};//把列车拆成两个点

    }

    sort(D+,D+tot+); V[].push_back((datt){,});//记得插入初始的点

    memset(val,0x7f,sizeof(val)); val[]=;//注意val是0x7f,加一点就会爆int

    for(int i=;i<=tot;i++)

    {

        int p=D[i].id,t=T[p].x;

        if(D[i].type) { push(p); continue; }

        while(int(V[t].size())-pos[t]> && V[t][pos[t]].res+calc(D[i].tim-V[t][pos[t]].tim) >= V[t][pos[t]+].res+calc(D[i].tim-V[t][pos[t]+].tim) )

            pos[t]++;

        if(pos[t]<int(V[t].size())) val[p]=V[t][pos[t]].res+calc(D[i].tim-V[t][pos[t]].tim);//更新val

        if(T[p].y==n&&val[p]<INF) ans=min(ans,val[p]+T[p].q);//注意有些火车坐不上,而val如果是0x7f,加上一个值就会爆掉

    }

    printf("%d\n",ans);

    return ;

}

顺便附上最暴力无脑的 $SPFA$：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(x=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+,M=,INF=2e9+;

struct Train{

    int x,y,p,q;

}T[N<<];

struct dat{

    int pos,tim;

};

queue <dat> Q;

vector <int> V[N];

int n,m,A,B,C,ans=INF;

inline int clac(int t) { return A*t*t+B*t+C; }

int dis[N][M];

bool vis[N][M];

int main()

{

    freopen("route.in","r",stdin);

    freopen("route.out","w",stdout);

    n=read(),m=read(),A=read(),B=read(),C=read();

    int a,b,c,d;

    for(int i=;i<=m;i++)

    {

        a=read(),b=read(),c=read(),d=read();

        T[i]=(Train){a,b,c,d};

        V[a].push_back(i);

    }

    memset(dis,0x7f,sizeof(dis));

    Q.push((dat){,}); vis[][]=; dis[][]=;

    while(!Q.empty())

    {

        dat x=Q.front(); Q.pop(); vis[x.pos][x.tim]=;

        int len=V[x.pos].size();

        for(int i=;i<len;i++)

        {

            int &p=V[x.pos][i]; if(x.tim>T[p].p) continue;

            int cst=clac(T[p].p-x.tim);

            if(dis[T[p].y][T[p].q]>dis[x.pos][x.tim]+cst)

            {

                dis[T[p].y][T[p].q]=dis[x.pos][x.tim]+cst;

                if(!vis[T[p].y][T[p].q]) Q.push((dat){T[p].y,T[p].q}),vis[T[p].y][T[p].q]=;

            }

        }

    }

    for(int i=;i<=m;i++) if(T[i].y==n) ans=min(ans,dis[n][T[i].q]+T[i].q);

    printf("%d\n",ans);

    return ;

}

SPFA

巴特西

P5468 [NOI2019]回家路线

最新文章

热门文章