P10769 「CROI · R2」公交接驳

Genius_Star · 2026-01-19 12:19:03 · 题解

或许更好的阅读体验。

思路：

题意比较复杂。

我们称一个班车管辖一个换乘站当且仅当这个班车是最先到达这个换乘站（或者同时到达且价值更小），称其实际管辖当且仅当到达的时间大于等于列车到换乘站的时间。

然后容易发现对于两个班车，如果一个班车在某一个换乘站上比另外一个更早到达，那么之后一定是这个班车领先；所以每个班车管辖的区域一定是以其始发站开头的前缀（或者压根没有，这没必要考虑）。

然后考虑最重要的性质保证两个换乘站之间乘坐公交车花费的时间一定不小于乘坐市郊铁路花费的时间；这说明每个班车实际管辖的范围一定是一个区间，即可能我一个前缀中的站我先到了但是列车还没到。

考虑一个被实际管辖的极长区间 [l, r]，为了使得总等待时间最小，显然希望在 t_l 时刻时班车恰好到了 l；此时总等待时间固定，于是期许的是班车的 v 尽可能小，容易想到找到前缀 [1, l] 中 v 最小的站 p 在 t_l - \operatorname{dis}(p, l) 发车。

那么对于这样一个序列 1 \sim n 的划分，能否保证对于每个班车实际管辖的是我们期望的呢？归纳证明一下，此时 <l 的位置归纳满足要求，考虑新增了 [l, r] 的班车在 p 处发车：

• 考虑 [l, r] 的上一个区间 [l', l - 1]，如果 l' \ge p：那么 [l', l - 1] 的班车也是在 p 处时刻 t_{l'} - \operatorname{dis}(p, l') 发车的，根据之前的性质 t_l - \operatorname{dis}(p, l) \ge t_{l'} - \operatorname{dis}(p, l')，即 [l, r] 的班车先发车，考虑其到 l' 的时刻 t_l - \operatorname{dis}(p, l) + \operatorname{dis}(p, l') = t_l -\operatorname{dis}(l, l') \le t_{l'}，那么到 l' 时列车还没开到（或者恰好一起走了不劣），得证。

• 否则 l' < p：首先需要证明 p 处发车时刻小于等于 [l', l - 1] 的车到 p 的时刻即可，即 t_l - \operatorname{dis}(p, l) \le t_{l'} + \operatorname{dis}(l', p)，即 t_l - t_{l'} \le \operatorname{dis}(p, l) + \operatorname{dis}(l', p) = \operatorname{dis}(l', l)，这是题目给的性质；还要证明 [l', l - 1] 的车到 l 时 \ge t_l，这也是那个性质，于是得证。

上面还需要讨论价值相同比较到达时间的情况，但是较为简单，就不说了。

于是可以令 v 为 v 的前缀 \min，然后定义 dp_{i, j} 表示考虑前 i 个站已经发了 j 班车且最后一班车实际管辖的是以 i 结尾的最小代价，于是有转移：

令 S 为 s 的前缀和，那么：

于是预处理 w(l, r) 后即可做到 O(pn^2k)，注意到 k \ge n 时答案是 0，于是可以做到 O(pn^3)。

打表 w(l, r) 并不困难，你容易暴力验证其满足四边形不等式，于是满足决策单调性，直接套分治就可以做到 O(pn^2 \log n)。

证明一下：

考虑证明 w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)，抵消一下等价于 v_{i + 1} (S_j - S_i + t_{i + 1} - t_{j + 1})\le v_i (S_j - S_{i - 1} + t_i - t_{j + 1}) = v_i(S_j - S_i + t_i - t_{j + 1} + s_i)，先消掉一些于是 v_{i + 1}t_{i + 1} \le v_i(t_i + s_i)，而 t_{i + 1} \le t_i + s_i 是显然满足的，于是得证。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1010;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int T, n, q, k;
int s[N], v[N], t[N];
ll W[N][N], dp[N][N];
inline void init(){
    for(int i = 1; i <= n; ++i)
      for(int j = i; j <= n; ++j)
        W[i][j] = W[i][j - 1] + 1ll * v[i] * (s[j - 1] - s[i - 1] + t[i] - t[j]);
}
inline ll getw(int l, int r){
    return W[l][r];
}
inline void solve(int l, int r, int kl, int kr, int x){
    if(l > r || kl > kr)
        return ;
    int mid = (l + r) >> 1, kmid = -1;
    for(int i = kl; i <= min(mid - 1, kr); ++i){
        if(kmid == -1 || dp[x - 1][i] + getw(i + 1, mid) < dp[x][mid]){
            dp[x][mid] = dp[x - 1][i] + getw(i + 1, mid);
            kmid = i;
        }
    }
    solve(l, mid - 1, kl, kmid, x);
    solve(mid + 1, r, kmid, kr, x);
}
inline void solve(){
    for(int i = 1; i <= n; ++i)
      t[i] = read();
    init();
    for(int i = 1; i <= n; ++i)
      dp[1][i] = getw(1, i);
    for(int x = 2; x < n; ++x)
      solve(1, n, 0, n, x);
    q = read();
    while(q--){
        k = read();
        if(k >= n)
          putchar('0');
        else
          write(dp[k][n]);
        putchar(' ');
    }
    putchar('\n');
}
int main(){
    n = read();
    for(int i = 1; i < n; ++i)
      s[i] = read() + s[i - 1];
    for(int i = 1; i <= n; ++i){
        v[i] = read();
        if(i > 1)
          v[i] = min(v[i], v[i - 1]);
    }
    T = read();
    while(T--)
      solve();
    return 0;
}
``