NOI 2020 美食家：广义矩阵乘法与拆点技巧的数学解剖
在解决 NOI 2020《美食家》时，仅仅知道“矩阵快速幂 + 拆点”的算法名词是不够的。本文将从数学底层出发，详细剖析广义矩阵乘法 (Max-Plus Algebra) 的合法性，并用严谨的数学定义和实例展示拆点构造与向量优化的过程。
一、 数学基础：Max-Plus 代数 (热带半环)
普通动态规划的转移方程为：
我们希望将其转化为矩阵乘法的形式，以便利用结合律进行快速幂加速。这就引入了 Max-Plus 代数 (Tropical Semiring)。
1. 广义运算的定义
我们重新定义两个实数上的基本运算：
广义加法：定义为取最大值，即 $ a \oplus b = \max(a, b) $
广义乘法：定义为普通加法，即 $ a \otimes b = a + b $
在这种代数系统中：
零元 (Identity for $\oplus$)：$ -\infty $。因为 $ \max(a, -\infty) = a $。
幺元 (Identity for $\otimes$)：$ 0 $。因为 $ a + 0 = a $。
2. 矩阵乘法的同构映射
基于上述标量运算，我们定义广义矩阵乘法 $ C = A \otimes B $。 对于矩阵 $ A $ (大小 $ m \times n $) 和 $ B $ (大小 $ n \times p $)，新矩阵 $ C $ (大小 $ m \times p $) 的元素定义为：
$$ C_{i,j} = \bigoplus_{k=1}^{n} (A_{i,k} \otimes B_{k,j}) = \max_{1 \leq k \leq n} (A_{i,k} + B_{k,j}) $$
结合律的证明（关键）： 为了能使用快速幂，矩阵乘法必须满足结合律 $ (A \otimes B) \otimes C = A \otimes (B \otimes C) $。 证明其标量形式满足分配律：
$$ a \otimes (b \oplus c) = a + \max(b, c) = \max(a + b, a + c) = (a \otimes b) \oplus (a \otimes c) $$
由于标量运算满足分配律和结合律，广义矩阵乘法必然满足结合律。因此我们可以安全地计算 $ A^n $。
二、 拆点技巧的数学模型与实例
题目中边权（天数）$ w \in [1,5] $，导致转移不仅依赖上一天，还依赖前 5 天的状态。这破坏了标准马尔可夫性（即只依赖上一状态）。我们需要在状态空间上进行扩维（拆点）。
1. 状态映射定义
设原图节点集为 $ V $，边集为 $ E $。 构建新状态集 $ V' = \{(u, t) \mid u \in V, t \in \{0, 1, 2, 3, 4\} \} $，总维度为 $ 5|V| $。 状态 $ (u, t) $ 的物理意义是：“目标是节点 $ u $，且距离真正到达 $ u $（获取愉悦值）还有 $ t $ 天在路上。”
2. 边权转移矩阵 $ T $ 的构造
矩阵 $ T $ 大小为 $ 5|V| \times 5|V| $，初始所有元素为 $ -\infty $。
内部等待边 (时间流逝)： 对于每个节点 $ u $ 和 $ t \in \{1, 2, 3, 4\} $，连边：
$$ T[(u, t), (u, t-1)] = 0 $$
_(数学含义：今天距离到达 $ u $ 还有 $ t $ 天，过了一天后，距离到达还有 $ t-1 $ 天，愉悦值增加 0)_
图上实际边 (发起移动)： 对于原图中的每一条边 $ u \to v $，边权为 $ w $，目标点价值为 $ val_v $：
$$ T[(u, 0), (v, w-1)] = val_v $$
_(数学含义：目前已经处于点 $ u $ ($ t=0 $)，决定走向 $ v $。因为需要花费 $ w $ 天，相当于瞬间进入了“距离到达 $ v $ 还有 $ w-1 $ 天”的状态，并提前把 $ val_v $ 的奖励锁定。)_
3. 具体构造实例 (图文并茂)
假设有一个极简的原图：
点集：
1, 2。 价值：$ val_1 = 10, val_2 = 20 $。
边集只有一条：
1 -> 2，花费天数 $ w = 3 $。
新状态编号分配： 我们只需拆分到最大边权，设
(1,0) 为行 1，(2,0) 为行 2，(2,1) 为行 3，(2,2) 为行 4。
状态转移图解：
对应的广义邻接矩阵 $ T $ 如下：
(1,0) (2,0) (2,1) (2,2)
(1,0) -∞ 20 -∞ -∞
(2,0) -∞ -∞ -∞ -∞
(2,1) -∞ -∞ -∞ -∞
(2,2) -∞ -∞ 0 -∞
如果我们对初始状态向量 $ S = [0, -\infty, -\infty, -\infty] $ 乘以 $ T $ 发生 3 次转移：
1. $ S \cdot T = [-\infty, 20, -\infty, -\infty] $ _(获得 20，处于 (2,2))_
2. $ S \cdot T^2 = [-\infty, -\infty, 20, -\infty] $ _(处于 (2,1))_
3. $ S \cdot T^3 = [-\infty, -\infty, -\infty, 20] $ _(最终到达 (2,0)，完美耗时 3 天 )_
三、 时间轴拆分与“向量乘法”降维打击
这是本题拉开分数差距的核心数学优化。
题目有 $ K $ 个美食节，发生时间为 $ t_1, t_2, ..., t_K $。我们需要在特定时间点强行修改向量的值。 假设没有优化，时间差为 $ \Delta t $，转移公式为：
$$ S_{\text{new}} = S_{\text{old}} \cdot T^{\Delta t} $$
1. 复杂度的数学计算
计算 $ T^{\Delta t} $：需要进行 $ O(\log \Delta t) $ 次矩阵乘法。
矩阵×矩阵复杂度：$ O((5n)^3) = O(125n^3) $，这里 $ n \leq 50 $。
2. 利用结合律进行降维
我们注意到，每次都是一个 $ 1 \times 5n $ 的行向量 去乘一个 $ 5n \times 5n $ 的矩阵。 根据结合律，我们可以预先计算好所有的 $ T^{2^i} $。
预处理复杂度：$ O(\log T) $ 个矩阵相乘，耗时 $ O(125n^3 \log T) $（完全可以接受）。
在实际跳跃 $ \Delta t $ 步时，将 $ \Delta t $ 二进制分解 $ \Delta t = \sum 2^i $。 则状态更新可以写为：
$$ S := S \cdot T^{2^{i_1}} \cdot T^{2^{i_2}} \cdot ... \cdot T^{2^{i_k}} $$
注意：向量×矩阵 的时间复杂度是 $ O((5n)^2)= O(25n^2) $！ 在计算时，我们严格按照从左到右的顺序结合：
for i in range(MAX_LOG):
if (delta_t >> i) & 1:
S = multiply_vector_matrix(S, T_power[i])
这样，每次美食节事件的跳跃只需执行 $ O(\log T) $ 次向量乘矩阵。 单次事件复杂度下降为 $ O(25n^2 \log T) $。 总复杂度骤降至 $ O(K \cdot 25n^2 \log T) $，轻松跑进 1 秒内。
四、 总结
1. Max-Plus 代数为我们在图上求最长路 / 最大收益提供了矩阵快速幂的合法数学外衣。
2. 拆点本质上是通过增加有限的维度空间 $ 5|V| $，来消除状态转移中的延迟依赖，使其恢复一阶马尔可夫性。
3. 向量乘矩阵结合律优先 是矩阵加速类题目中处理“多阶段离散干预”的神级技巧，实现了 $ O(n^3) \to O(n^2) $ 的降维打击。