月球疏散行动

· · 题解

有幸参加过这场蓝桥。省一国三。印象很深刻的是当时国赛被一个运算式一个数独一个摆渡车创飞了。可以看看省赛的 游记，图个乐。

发现洛谷把题搬过来了，写篇题解。也算是追忆我两年前学 oi 的快乐时光了。

依赖 T 的做法题解区挺多的。这里说说不依赖 T 的 \mathcal{O(n^2m)} 做法。

首先考虑 f_i 表示前 i 个人都疏散了的等待时间最小值。转移时对于 i 可以枚举最后一个乘上一辆穿梭机的人 j，计算 j+1 \sim i 人的等待时间。

但是这样有个问题，不知道 j 上穿梭机的时间，也就是不知道 i 这辆穿梭机的到达时间。这样是不对的。我们不能认为 T_j 就是 j 上穿梭机的时间。如果有读者写了类似的思路，可以尝试这个 hack：

Input:
10 2 
92 93 94 95 95 95 96 97 98 98
Output:
5

只能把这个东西压入状态。f_{i,j} 表示前 i 个人，都在 j 时刻及之前疏散了。上了穿梭机不妨也假定已经疏散了，方便计算。

这样对于 i，枚举上一个乘坐上一辆穿梭机的人 j，再枚举 j 上穿梭机的时间 k。那么 \max(T_j, k + m) 就是穿梭机的到达时间。

可是这样 j 又是 T 的量级了。这里需要一个观察：每个人至多只会等待 m-1 分钟。所以 j \in [t_i, t_i + m - 1]。j 也就是 m 的量级。

优化一下状态：f_{i,j} 表示前 i 个人都已疏散，第 i 个人刚好等了 j 分钟的最小等待时间。

对 i 转移时枚举上一个乘上一班穿梭机的人 j，再枚举 j 的等待时间 k，即可得到本班车的到达时间 \max(T_j + k + m, T_i)，计算编号为 (j + 1)\sim i 人的等待时间即可，这里使用前缀和优化。最终时间复杂度 \mathcal{O(n^2m)}。常数较小。

转移部分代码：

mem(f, 0x3f);
f[0][0] = 0; 
for (ll i = 1; i <= n; ++ i )
{
    for (ll j = 0; j < i; ++ j )
    {
        for (ll k = 0; k < m; ++ k )
        {
            ll d = (j == 0 ? 0 : max(0ll, t[j] + k + m - t[i]));
            f[i][d] = min(f[i][d], f[j][k] + getv((j == 0 ? t[i] : max(t[j] + k + m, t[i])), j + 1, i)); // getv 为计算代价
        }
    }
}

实际上，可以进一步优化到 \mathcal{O(nm\log m)} 或 \mathcal{O(nm)}。笔者能力有限就不介绍了。

代码：code