LibreOJ 3156 「NOI2019」回家路线

所以……其实是 NOI 赛场上不可多得的送分题？
我还调了这么久……

首先设 fi 表示坐了第 i 班列车后的最小烦躁值（这里先不考虑 qsk）。
有转移 fi=minqj≤pi,yj=xi(fj+A(pi−qj)2+B(pi−qj)+C)

这怎么这么像「『APIO2010』特别行动队」啊？
先不管 yj=xi 的限制，考虑斜率优化。
设决策 qk≤qj≤pi 满足 j 优于 k 即 fj+A(pi−qj)2+B(pi−qj)+C<fk+A(pi−qk)2+B(pi−qk)+Cfj−2Apiqj+Aq2j−Bqj<fk−2Apiqk+Aq2k−Bqk(fj+Aq2j)−(fk+Aq2k)<2Api(qj−qk)(fj+Aq2j)−(fk+Aq2k)qj−qk<2Api

注意判掉 qj=qk 的情况，这时斜率就当做 −∞ 来处理。
（然鹅不判也能过……）

于是我们发现，如果我们按照时间轴来 DP 的话，就是一个标准的斜率优化。 即，在时间点 i 将 qj=i 的 j 加入候选决策集合，并对 pj=i 的 fj 进行转移。

然鹅还有一个问题：yj=xi。
这个可以对每一个站点都开一个队列解决。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int T = 1e3;
int n,m,A,B,C;
struct note
{
    int x,y,p,q;
} a[M + 5];
vector<int> st[T + 5],ed[T + 5];
int f[M + 5],vis[M + 5],ans = 0x3f3f3f3f;
struct Queue
{
    vector<int> q;
    int head,tail;
    Queue()
    {
        head = 0,tail = -1;
    }
    inline void push(int x)
    {
        q.push_back(x),++tail;
    }
    inline void pop_front()
    {
        ++head;
    }
    inline void pop_back()
    {
        --tail,q.pop_back();
    }
    inline int size()
    {
        return tail - head + 1;
    }
    inline const int &operator[](int x)
    {
        return q[x];
    }
    inline const int &front()
    {
        return q[head];
    }
    inline const int &after_front()
    {
        return q[head + 1];
    }
    inline const int &back()
    {
        return q[tail];
    }
    inline const int &before_back()
    {
        return q[tail - 1];
    }
} q[N + 5];
inline double slope(int x,int y)
{
    if(a[x].q == a[y].q)
        return -0x3f3f3f3f3f3f3f3f;
    return (double)(f[x] + A * a[x].q * a[x].q - B * a[x].q - f[y] - A * a[y].q * a[y].q + B * a[y].q) / (a[x].q - a[y].q);
}
int main()
{
    freopen("route.in","r",stdin),freopen("route.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].p,&a[i].q);
    for(register int i = 1;i <= m;++i)
        st[a[i].p].push_back(i),ed[a[i].q].push_back(i);
    q[1].push(0);
    for(register int i = 1;i <= T;++i)
    {
        for(register int j = 0;j < ed[i].size();++j)
            if(vis[ed[i][j]])
            {
                int k = ed[i][j];
                for(;q[a[k].y].size() >= 2 && slope(q[a[k].y].before_back(),q[a[k].y].back()) > slope(q[a[k].y].back(),k);q[a[k].y].pop_back());
                q[a[k].y].push(k);
            }
        for(register int j = 0;j < st[i].size();++j)
        {
            int k = st[i][j];
            for(;q[a[k].x].size() >= 2 && slope(q[a[k].x].front(),q[a[k].x].after_front()) < 2.0 * A * i;q[a[k].x].pop_front());
            if(q[a[k].x].size())
            {
                f[k] = f[q[a[k].x].front()] + A * (i - a[q[a[k].x].front()].q) * (i - a[q[a[k].x].front()].q) + B * (i - a[q[a[k].x].front()].q) + C;
                vis[k] = 1;
                if(a[k].y == n)
                    ans = min(ans,f[k] + a[k].q);
            }
        }
    }
    printf("%d\n",ans);
}