所以……其实是 NOI 赛场上不可多得的送分题？
我还调了这么久……
首先设 \(f_i\) 表示坐了第 \(i\) 班列车后的最小烦躁值（这里先不考虑 \(q_{s_k}\)）。
有转移 \[f_i = \min\limits_{q_j \le p_i,y_j = x_i}(f_j + A(p_i - q_j)^2 + B(p_i - q_j) + C)\]
这怎么这么像「『APIO2010』特别行动队」啊？
先不管 \(y_j = x_i\) 的限制，考虑斜率优化。
设决策 \(q_k \le q_j \le p_i\) 满足 \(j\) 优于 \(k\) 即 \[\begin{align*}
f_j + A(p_i - q_j)^2 + B(p_i - q_j) + C & < f_k + A(p_i - q_k)^2 + B(p_i - q_k) + C \\
f_j - 2Ap_iq_j + Aq_j^2 - Bq_j & < f_k - 2Ap_iq_k + Aq_k^2 - Bq_k \\
(f_j + Aq_j^2) - (f_k + Aq_k^2) & < 2Ap_i(q_j - q_k) \\
\dfrac{(f_j + Aq_j^2) - (f_k + Aq_k^2)}{q_j - q_k} & < 2Ap_i
\end{align*}\]
注意判掉 \(q_j = q_k\) 的情况，这时斜率就当做 \(-\infty\) 来处理。
（然鹅不判也能过……）
于是我们发现，如果我们按照时间轴来 DP 的话，就是一个标准的斜率优化。 即，在时间点 \(i\) 将 \(q_j = i\) 的 \(j\) 加入候选决策集合，并对 \(p_j = i\) 的 \(f_j\) 进行转移。
然鹅还有一个问题：\(y_j = x_i\)。
这个可以对每一个站点都开一个队列解决。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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);
}