【题解】Luogu P5468 [NOI2019]回家路线

水深无声 2021-10-30 03:22 299阅读 0赞

### [原题传送门][Link 1] ###

### 前置芝士：斜率优化 不会的可以去[杜神博客][Link 2]学 ###

#### 这道题我考场上只会拆点跑最短路的70pts做法 ####

#### 后来回家后发现错误的爆搜都能拿满分（刀片） ####

#### 还有很多人\\(O(mt)\\)过的，还是要坚持写正解好不好 ####

#### 我们先考虑\\(O(mt)\\)的暴力dp，先不考虑总时间对烦躁值的影响，设\\(dp\[id\]\\)表示走完第\\(id\\)条边最小的代价： ####

\\\[dp\[id\]=Min(dp\[j\]+A(p\_\{id\}-q\_j)^2+B(p\_\{id\}-q\_j)+C)(id,j \\in \[1,m\],q\_j<=p\_\{id\},v\[j\]=u\[id\])\\\]

#### 看着这个方程有平方项考虑展开，展开后会发现能转化成斜率优化标准形式 ####

\\\[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-C\\) ####

#### 每条边进出一次队列，所以复杂度为\\(O(m)\\) ####

#### 完整代码 ####

#include <bits/stdc++.h>
    #define N 200005
    #define ll long long
    #define db double
    #define getchar nc
    using namespace std;
    inline char nc(){
        static char buf[100000],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read()
    {
        register int x=0,f=1;register char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
        return x*f;
    }
    inline void write(register ll x)
    {
        if(!x)putchar('0');if(x<0)x=-x,putchar('-');
        static int sta[20];register int tot=0;
        while(x)sta[tot++]=x%10,x/=10;
        while(tot)putchar(sta[--tot]+48);
    }
    inline int Max(register int a,register int b)
    {
        return a>b?a:b;
    }
    inline ll Min(register ll a,register ll b)
    {
        return a<b?a:b;
    }
    struct node{
        ll x,y;
        int id;
    };
    int n,m,A,B,C,maxT=0;
    int x[N],y[N],p[N],q[N],head[N];
    ll ans=1926081700000000ll,dp[N];
    vector<int> d[1005];
    vector<node>que[N];
    queue<int> res[1005];
    inline db gslope(register node a,register node b)
    {
        return 1.0*(a.y-b.y)/(1.0*(a.x-b.x));
    }
    inline void ins(register int id)
    {
        int pos=y[id];
        node now=(node){q[id],dp[id]+A*q[id]*q[id]-B*q[id],id};
        while(que[pos].size()-head[pos]>=2)
        {
            int len=que[pos].size();
            if(gslope(que[pos][len-1],que[pos][len-2])<gslope(que[pos][len-2],now))
                break;
            que[pos].pop_back();
        }
        que[pos].push_back(now);
    }
    inline void del(register db slpe,register int pos)
    {
        while(que[pos].size()-head[pos]>=2)
        {
            if(gslope(que[pos][head[pos]],que[pos][head[pos]+1])>slpe)
                return;
            ++head[pos];
        }
    }
    int main()
    {
        n=read(),m=read(),A=read(),B=read(),C=read();
        for(register int i=1;i<=m;++i)
            x[i]=read(),y[i]=read(),p[i]=read(),q[i]=read(),maxT=Max(maxT,q[i]);
        for(register int i=1;i<=m;++i)
            d[p[i]].push_back(i);
        que[1].push_back((node){0,0,0});
        for(register int t=0;t<=maxT;++t)
        {
            while(!res[t].empty())
                ins(res[t].front()),res[t].pop();
            int len=d[t].size();
            for(register int k=0;k<len;++k)
            {
                int id=d[t][k];
                int pos=x[id];
                if(que[pos].size()==head[pos])
                    continue;
                db slpe=2.0*A*p[id];
                del(slpe,pos);
                int j=que[pos][head[pos]].id;
                dp[id]=dp[j]+1ll*A*(p[id]-q[j])*(p[id]-q[j])+1ll*B*(p[id]-q[j])+C;
                res[q[id]].push(id);
                if(y[id]==n)
                    ans=Min(ans,dp[id]+q[id]);
            }
        }
        write(ans);
        return 0;
    }

转载于:https://www.cnblogs.com/yzhang-rp-inf/p/11198638.html

[Link 1]: https://www.luogu.org/problemnew/show/P5468
[Link 2]: https://www.luogu.org/blog/top-oier/qian-tan-xie-shuai-you-hua