[NOI2020] 美食家 题解

属于是将矩阵快速幂的绝大部分技巧用到了极致的一道题。

暴力部分

首先我们先考虑一个普通 DP。

定义 \(dp_{t,i}\) 表示在时间为 \(t\) 时到达点 \(i\) 可以得到的愉悦值之和的最大值。

显然有 \((i,j)\in E \to dp_{t+w,j}=\max(dp_{t,i}+c_j)\)。特判一下当前节点有美食节的情况即可，复杂度 \(\mathcal{O}(T\times (n+m))\)。

矩阵快速幂&拆点优化

我们先暂时不考虑美食节的情况，这个后面再处理。

观察到这个 \(T\) 非常的大，但是 \(dp_t\to dp_{t+w}\) 这个东西不太好，我们当然希望是按照普通的矩阵快速幂一样，是用 \(dp_{t}\to dp_{t+1}\) 的转移矩阵进行矩阵快速幂优化。

我们考虑矩阵快速幂中一个拆点/拆边的技巧。（为啥我不知道捏）

首先一个直观的，对于边 \((i,j,w)\)，你可以把他拆成 \((i,e_1,0),(e_1,e_2,0),....(e_{w-1},j,c_j)\)。（拆掉之后这个三元组的含义也变了，最后那个是边权）

这样你的转移式就变成了 \(dp_{t,i}+w\to dp_{t+1,j}\)。这样就非常容易使用矩阵快速幂优化了。

当然这里有个小细节，由于 DP 是求的 \(\max\) 这里是 \(\max\) 加矩阵乘法，不是普通的矩阵乘法，这里说明一下。

但是这样的话，复杂度仍然达到了 \(\mathcal{O}((n+4\times m)^3\times \log T)\)

我们发现这个 \(n,m\) 根本就不同阶，考虑把拆边变为拆点。

具体来说，我们将点 \(i\) 拆成 \(i_1 \to i_2 \to i_3\to i_4 \to i_5\) 边权均为 \(0\)，对于原图上的边 \((i,j,w)\) 对应在拆了点的图上就是 \((i_w,j_1,c_j)\)，可以发现这样的策略与刚刚拆边的效果是等价的。

此时时间复杂度来到 \(\mathcal{O}((5\times n)^3\times \log T)\)

特殊点处理

在进行了进一步的优化之后，此时我们就需要考虑一下美食节的问题了。

由于美食节会将 \(t_i\) 时，\(c_{x_i}+y_i\)，改变我们的转移矩阵。故我们考虑将 \(t_i\) 看作特殊点，先求出 \(t_i-1\) 时的 \(dp_{t_i-1,x}\)，然后对于 \(dp_{t_i,x}\) 进行暴力的 \(\mathcal{O}(n+m)\) 转移，然后再求出 \(t_{i+1}-1\) 的 \(dp_{t_{i+1}-1,x}\) 的值..... 依此类推。

时间复杂度 \(\mathcal{O}(k\times (n+m)+k\times (5\times n)^3\times \log T)\)。

向量乘矩阵优化

我们发现我们为了求出 \(t_i-1\) 时的 \(dp\) 值，每次都需要进行 \(\mathcal{O}(5\times n)^3\times \log T)\) 的矩阵快速幂。

有一个很逆天的东西是，转移矩阵自乘的时间复杂度是 \(\mathcal{O}((5\times n)^3)\)，但是初始矩阵乘转移矩阵复杂度是 \(\mathcal{O}((5\times n)^2)\)，而在我们的特殊点处理中我们进行了多次快速幂，大大增加了转移矩阵的自乘。

假设转移矩阵是 \(G\)，我们考虑预处理出 \(G^{2^0},G^{2^1},...G^{2^{\log T}}\) 的所有矩阵，这样我们的每次快速幂就是用初始矩阵乘以转移矩阵，快速幂的总进行复杂度就减少为了 \(\mathcal{O}((5\times n)^2\times \log T \times k)\)，总复杂度加上这个预处理就是 \(\mathcal{O}(k\times (n+m)+k\times (5\times n)^2\times \log T+(5\times n)^3\times \log T)\)，发现此时可以通过。

代码暂时咕咕咕了。