xy0v0's Blog

Back

题目#

在计算机体系结构领域,缓存能保存先前访问过的合适数据,从而加快重复的内存访问。在最久未使用 (LRU) 策略下,向已满的缓存中插入新项时,会淘汰其中最长时间未被访问的旧项。

为了简化问题,你决定在一个最多只能容纳两个不同地址的缓存上实验,并用一个包含 nn 次内存访问请求的序列进行测试,涉及的地址编号为 11 到 mm,其中第 ii 次请求访问地址 aia_i。初始时,缓存为空。

这些请求必须按原顺序处理。对于各请求,你可以分别选择以下两种方法之一:

  • 直接访问:直接从内存访问该地址。耗时 AA 个单位时间,且不会以任何方式影响缓存。
  • 缓存访问:通过缓存访问该地址。如果该地址已在缓存中,则发生一次缓存命中,耗时 BB 个单位时间,此时该地址仍保留在缓存中,并成为最近使用的地址。否则,发生一次缓存未命中,耗时 CC 个单位时间,此时将该地址作为最近使用的地址插入缓存,若缓存已满,则先移除最久未使用的地址。与现实的缓存一样,B≤CB \le C 始终成立。

求处理全部 nn 次请求所需的最少总时间。

输入格式

输入的第一行包含一个整数 TT(1≤T≤1051 \le T \le 10^5),表示测试数据组数。

每组数据的第一行包含五个整数 n,m,A,B,Cn, m, A, B, C(1≤n≤1051 \le n \le 10^5,1≤m≤min⁡(n,500)1 \le m \le \min(n, 500),1≤A,B,C≤1091 \le A, B, C \le 10^9,B≤CB \le C)。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤m1 \le a_i \le m),依次表示每次请求访问的地址。

保证所有数据中 nn 的和不超过 10510^5。

输出格式

对于每组数据,输出一行一个整数,表示最少总时间。

思路#

首先考虑朴素的 DP,记 dp[u][v] 代表缓存对为 (u,v) 时的最小代价,需要注意为有序数对,因为需要考虑元素的活跃先后。其中若有 u=0/v=0 代表该位缓存为空。

接下来讨论转移情况,加入新元素大致分为两种:在缓存中与不在缓存中。首先,无论加入什么元素,都可以选择直接访问,即 dp[u][v]+A 。接下来考虑利用缓存读入,记当前加入元素为 x ,若有 x=u ,则转移为 dp[v][u]+B ,若有 x=v ,则转移为 dp[u][v]+B ,以上两种情况之外则有 dp[v][x]+C 。

以上朴素做法复杂度为 O(nm2)O(nm^2) ,代码实现如下:

这里引入 ndp 是因为需要对 dp 中的原值反复访问,不能直接修改原 dp 。

接下来考虑优化:

先考虑缓存访问,注意到无论如何,缓存访问后第二位都是当前访问的元素。首先考虑缓存未击中情况下的缓存访问,对于任意的 (u,v) 执行一次未击中的缓存访问( v≠xv\ne x ),变为 (v,x) ,若正在求解 (k,x) ,则只需要考虑所有 v=k 情况下的最小值即可,又由于 B≤CB\le C ,不必特别考虑 u=x 的情况,因为取最小值时不会影响答案。

又由于所有直接访问都会加上 A ,只需要考察当前方式相比全部直接访问多花的代价,那么考虑 x 时候只需要修改 v=x 的值,其他必定都是直接访问,不会改变值,可将复杂度降至 O(nm)O(nm) ,维护每列最小值即可。

代码#

补题 | 2026沈阳 C

https://www.xy0v0.top/blog/shenyang-2026-c
Author xy0v0 Published at Copyright CC BY-NC-SA 4.0