题解 [USACO23DEC] Train Scheduling P

一个似乎和官方题解不太一样的一个做法。

首先考虑一个转化：假设连接两个车站的并不是一条轨道，而是一对单向的超距传送门。此时任意一辆车都可以从传送门的入口瞬移到出口，但是传送门改变方向需要 TT 的时间。容易证明这样转化和原问题是等价的。

然后我们将发车时刻离散化，并进行一个贡献提前计算的 dp：记 fi,j,0/1f_{i,j,0/1} 表示到第 ii 个时刻，有 jj 个车在等待发车，传送门此时的方向是从 A 到 B / 从 B 到 A，所有已经可以发车的车的等待时间总和的最小值。

转移有两种。第一种是不在第 ii 个时刻开始改变传送门的方向，转移方程如下：

fi,j,k+j⋅(ti+1−ti)→fi,j+ci+1,1−k,kf_{i,j,k}+j\cdot (t_{i+1}-t_i)\rightarrow f_{i,j+c_{i+1,1-k},k}

其中 tt 是第 ii 个时刻对应的具体时刻（因为进行了离散化），ci,0/1c_{i,0/1} 是在第 ii 个时刻发车，方向是从 A 到 B / 从 B 到 A 的车的个数。直接转移的复杂度即为 O(N2)O(N^2)。

第二种是在第 ii 个时刻 tit_i 时开始改变传送门的方向，到 ti+Tt_i+T 时完成改变，并立刻发出所有正在等待且方向正确的车；并立刻开始下一次改变，到 ti+2Tt_i+2T 时将方向改变回来，并立刻发出所有正在等待且方向正确的车，以此类推重复反向若干次。

此时我们需要枚举反向的次数 cc，并设 i′i' 为第一个满足 ti′>ti+cTt_{i'}>t_i+cT 的时刻。假设此时等待的车数和 原定在时刻 ii 之后发车的车 总共产生的代价分别为 j′j' 和 ww，那么有如下转移：

fi,j,k+jT+w→fi′,j′,(k+c) mod 2f_{i,j,k}+jT+w\rightarrow f_{i',j',(k+c)\bmod 2}

其中 j′j' 和 ww 都可以在递增枚举 cc 的过程中同步计算得到。

直接进行这个转移需要枚举 cc，时间复杂度和值域有关，无法接受。但是我们不难发现：如果连续进行了两次反向，而这两次反向所占用的长度为 2T2T 的时间区间内不包含任何一个原定的发车时间点，那么我们一定不需要进行更多的连续反向。于是我们可以在遇到这种情况时停止枚举。这样 cc 的枚举量下降到了 O(N)O(N)。

但是我们仍然需要枚举 i,j,ci,j,c 三个值，复杂度为 O(N3)O(N^3)。注意到 w,j′w,j' 都只和 i,c,ki,c,k 有关，和 jj 无关，因此我们可以先枚举 i,ki,k，在枚举 cc 之前预先求出最小的 fi,j,k+jTf_{i,j,k}+jT，再枚举 cc 进行转移。这样复杂度就下降到了 O(N2)O(N^2)，可以通过。

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
const int N = 5005;
int n, psz, typ[N], idx[N], pos[N];
long long T, stt[N], pol[N], dp[N][N][2], cnt[N][2];

inline void Read() {
    cin >> n >> T;
    for (int i = 1;i <= n;i++) {
        char c; cin >> c >> stt[i];
        pol[i] = stt[i];
        typ[i] = c - 'A';
        idx[i] = i;
    }
}

inline void Prefix() {
    sort(idx + 1, idx + n + 1, [&](const int &x, const int &y) {
        return stt[x] < stt[y];
    });
    for (int i = 1;i <= n;i++) pol[i] = stt[idx[i]];
    psz = unique(pol + 1, pol + n + 1) - pol - 1;
    pol[psz + 1] = 0x3f3f3f3f3f3f3f3f;
}

inline void Upd(long long &x, long long y) {
    x = min(x, y);
}

inline void Solve() {
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1;i <= n;i++) cnt[pos[i] = lower_bound(pol + 1, pol + psz + 1, stt[i]) - pol][typ[i]]++;
    idx[n + 1] = n + 1;
    pos[idx[n + 1]] = psz + 1;
    dp[1][cnt[1][0]][1] = 0;
    dp[1][cnt[1][1]][0] = 0;
    for (int i = 1;i <= psz;i++) {
        for (int k = 0;k < 2;k++) {
            long long mnv = 0x3f3f3f3f3f3f3f3f;
            for (int j = 0;j <= n;j++) {
                Upd(mnv, dp[i][j][k] + j * T);
                if (i != psz || j == 0) Upd(dp[i + 1][j + cnt[i + 1][!k]][k], dp[i][j][k] + j * (pol[i + 1] - pol[i]));
            }
            int pi = 0;
            while (pi < n && stt[idx[pi + 1]] <= pol[i]) pi++;
            long long ct = pol[i];
            int ck = k, w = 0, brf = 0;
            long long cst = 0;
            for (;;) {
                ct += T;
                int nxt = pi;
                cst += w * T;
                w = 0;
                while (nxt < n && stt[idx[nxt + 1]] <= ct) {
                    nxt++;
                    if (typ[idx[nxt]] == ck) w++;
                    cst += ct - stt[idx[nxt]];
                }
                if (nxt + 1 <= n) {
                    Upd(dp[pos[idx[nxt + 1]]][w + cnt[pos[idx[nxt + 1]]][ck]][!ck], mnv + cst + (stt[idx[nxt + 1]] - ct) * w);
                } else {
                    Upd(dp[psz + 1][w][!ck], mnv + cst);
                }
                if (pi == nxt) {
                    brf++;
                    if (brf >= 2) break;
                } else brf = 0;
                pi = nxt;
                ck = !ck;
            }
        }
    }
    cout << min(dp[psz + 1][0][0], dp[psz + 1][0][1]) << endl;
}

int main() {
    Read();
    Prefix();
    Solve();
    return 0;
}