Core Logic and Mathematical Principles
Modern CPUs do not directly read data from physical memory (RAM), but instead fetch data through a cache hierarchy consisting of L1, L2, and L3 caches. The smallest unit of data exchange between physical memory and the cache is the Cache Line, which is fixed at $64$ bytes in mainstream x86_64 architectures.
When a program attempts to access memory address $A$, the CPU triggers a cache hit check at the hardware level. If the data block containing $A$ is already in the cache, it is called a Cache Hit, with a delay of only a few clock cycles; if it is not, a Cache Miss occurs, and the CPU must suspend the current execution pipeline to issue a read request to physical memory via the bus, leading to a delay that can increase by two orders of magnitude (approximately 50-200 clock cycles).
To maximize the probability of a Cache Hit, CPUs are equipped with hardware prefetchers that exploit spatial locality: when accessing address $A$, the hardware automatically pulls all adjacent data that fills a Cache Line (64 bytes) from physical memory into the cache.
In C++, multi-dimensional arrays are laid out in memory in a row-major order. Let’s consider a two-dimensional array matrix[N][M], where each element is $S$ bytes in size. The mathematical formula that maps the two-dimensional coordinates $(i, j)$ to a one-dimensional physical memory address $\text{Addr}(i, j)$ is given by:
@@@MATH_BLOCK7@@@C[i][j] = \min{k=1}^{V} {A[i][k] + B[k][j]}@@@MATH_BLOCK8@@@dp[i][S] = \min{S' \subset S} {dp[i-1][S \setminus S'] + \text{cost}(S', S \setminus S')}$$
由于子集枚举复杂度为 $O(3^N)$，配合深度维度后总常数极大。如果将数组声明为 dp[13][1<<12]，最内层枚举二进制状态 $S$ 时，右侧维度的二进制内存地址呈完美线性增长，极高地提升了高速缓存的命中率，是这道题在 NOIP 评测机上不加剪枝也能强行卡时限通过的关键底层黑魔法。