Description
给定 (n) 点，这 (n) 个点由 (m) 班列车穿插连结。对于第 (i) 班列车，会在 (p_i) 时刻从 (x_i) 站点出发开向 (y_i) 站点，到站时间为 (q_i)。现在从 (1) 号节点出发，经过多次换乘到达节点 (n)。一次换乘是指对于两班列车，假设分别为 (u) 号与 (v) 号列车，若 (y_u = x_v) 并且 (q_u leq p_v)，那么小猫可以乘坐完 (u) 号列车后在 (y_u) 号站点等待 (p_v - q_u) 个时刻，并在时刻 (p_v) 乘坐 (v) 号列车。要求最小化路程中的烦躁值。烦躁值的计算方法是：给定参数 (A,B,C)，对于每次等待，假设等待了 (t) 个时刻，那么烦躁值增加 (A t^2 + B t + C)。另外如果在时刻 (T) 到达节点 (n)，则狂躁值再增加 (T)。
Limitations
(1 leq n,~m leq 2 imes 10^5)
(0 leq A leq 10,~~0 leq B,~C leq 10^6)
(1 leq p_i leq q_i leq 10^3)
保证 (1) 可以到达 (n)。
Solution
好像正解是以时间为状态DP来着……然而拿到这个题的第一反应是DP每条边到 (n) 的贡献。
考虑设 (f_i) 是第 (i) 条边开始出发，到达 (n) 号节点对烦躁值的最小贡献。于是有转移方程：
即
将与 (j) 无关的项提出大括号，得到
整理得
设 (g_i = A q_i^2 - Bq_i - p_i + C)，(h_i = Ap_i^2 + (B+1)p_j)
上式即为
移相得到
注意到 (g_i) 是一个与 (i) 有关的常数，那么最小化 (f_i) 只需要最小化 (f_i + g_i)
如果将 (f_j + h_j) 看作纵坐标， (q_j) 看作横坐标，上述方程可以看成一条斜率为常数 (2Aq_i) 的直线，在所有满足条件的 (j) 中选择一个点，使得直线过这个点，最小化直线在 (y) 轴上的截距 (f_i + g_i)。
那么所有满足条件的点显然在一个下突壳上，证明上可以考虑如果一个点不在下突壳上那么能找到一个更优的 (j)。
然后考虑如果 (i) 会从 (j) 转移过来，那么一定有 (q_i leq p_j)，又因为 (p_j < q_j)，因此 (q_i < q_j)，于是按照 (q) 的不升序进行排序即可。
在转移时，只需要在每个点维护一个凸壳表示所有可能被选择的点，然后再维护一个 set 记录该点上已经被计算但是没有插入凸壳的点。set 内部按照 (p) 的不升序排序，每次要转移一条边 (i) 的时候先将终点中 (p) 不小于 (q_i) 的边插入凸壳，由于转移是按照 (q_i) 的顺序进行的，已经被插入凸壳的点一定是合法可以转移的。
另外注意到 (q_i) 是单调不升的，于是斜率 (2Aq_i) 也是单调升的，再考虑到插入的横轴 (p_j) 也是单调不升的，因此可以使用单调队列维护每个点的凸壳即可。
需要注意的一点细节是凸壳的横轴是从大到小插入的，在维护的时候不要把大于号小于号写反。
一共进行了 (m) 次转移，每次转移复杂度 (O(1))，因此 DP 过程的时间复杂度是 (O(m))，但是由于进行了排序，且每条边插入在 set 中 1 次，所以整个算法的时间复杂度 (O(m log m))。
Code
#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
const int maxn = 200005;
const ll INF = 1ll << 50;
int n, m;
ll A, B, C, ans;
ll frog[maxn], g[maxn], h[maxn];
struct M {
int x, y, p, q;
inline bool operator<(const M &_others) const {
return this->q > _others.q;
}
};
M MU[maxn];
struct Cmp {
inline bool operator() (const int &_a, const int &_b) {
if (MU[_a].p != MU[_b].p) {
return MU[_a].p > MU[_b].p;
} else {
return _a < _b;
}
}
};
std::deque<int>Q[maxn];
std::set<int, Cmp>s[maxn];
int query(const int x);
void free(const int x, const int y);
void insert(const int x, const int y);
signed main() {
freopen("route.in", "r", stdin);
freopen("route.out", "w", stdout);
qr(n); qr(m); qr(A); qr(B); qr(C);
for (int i = 1; i <= m; ++i) {
qr(MU[i].x); qr(MU[i].y); qr(MU[i].p); qr(MU[i].q);
}
frog[m + 1] = 1ll << 50;
std::sort(MU + 1, MU + 1 + m);
for (int i = 1; i <= m; ++i) {
g[i] = A * MU[i].q * MU[i].q - B * MU[i].q - MU[i].p + C;
h[i] = A * MU[i].p * MU[i].p + (B + 1) * MU[i].p;
}
for (int i = 1; i <= m; ++i) if (MU[i].y == n) {
frog[i] = MU[i].q - MU[i].p;
s[MU[i].x].insert(i);
} else {
int y = MU[i].y;
free(y, MU[i].q);
int j = query(i);
if (!j) {
frog[i] = INF;
continue;
}
frog[i] = frog[j] + g[i] + h[j] - ((A * MU[i].q * MU[j].p) << 1);
s[MU[i].x].insert(i);
}
ans = 1ll << 50;
for (int i = 1; i <= m; ++i) if (MU[i].x == 1) {
ans = std::min(frog[i] + A * MU[i].p * MU[i].p + B * MU[i].p + C + MU[i].p, ans);
}
qw(ans, '
', true);
return 0;
}
void free(const int x, const int y) {
while (!s[x].empty()) {
auto u = *s[x].begin();
if (MU[u].p >= y) {
insert(x, u);
s[x].erase(u);
} else {
break;
}
}
}
inline std::pair<ll, ll> calc(const int x) {
return std::make_pair(frog[x] + h[x], 1ll * MU[x].p);
}
inline bool judge(const int x, const int y, const int z) {
auto i = calc(x), j = calc(y), k = calc(z);
return (k.first <= j.first) && ((i.first - k.first) * (i.second - j.second) < (i.first - j.first) * (i.second - k.second));
}
void insert(const int x, const int y) {
while (Q[x].size() > 1) {
int i = Q[x].back(); Q[x].pop_back(); int j = Q[x].back();
if (judge(j, i, y)) {
Q[x].push_back(i); break;
}
}
Q[x].push_back(y);
}
int query(const int p) {
int x = MU[p].y;
while (Q[x].size() > 1) {
int i = Q[x].front(); Q[x].pop_front(); int j = Q[x].front();
auto s = calc(i), t = calc(j); ll k = ((A * MU[p].q) << 1);
if ((k * (s.second - t.second)) > (s.first - t.first)) {
Q[x].push_front(i);
break;
}
}
return Q[x].size () ? Q[x].front() : 0;
}