题目#
在计算机体系结构领域,缓存能保存先前访问过的合适数据,从而加快重复的内存访问。在最久未使用 (LRU) 策略下,向已满的缓存中插入新项时,会淘汰其中最长时间未被访问的旧项。
为了简化问题,你决定在一个最多只能容纳两个不同地址的缓存上实验,并用一个包含 次内存访问请求的序列进行测试,涉及的地址编号为 到 ,其中第 次请求访问地址 。初始时,缓存为空。
这些请求必须按原顺序处理。对于各请求,你可以分别选择以下两种方法之一:
- 直接访问:直接从内存访问该地址。耗时 个单位时间,且不会以任何方式影响缓存。
- 缓存访问:通过缓存访问该地址。如果该地址已在缓存中,则发生一次缓存命中,耗时 个单位时间,此时该地址仍保留在缓存中,并成为最近使用的地址。否则,发生一次缓存未命中,耗时 个单位时间,此时将该地址作为最近使用的地址插入缓存,若缓存已满,则先移除最久未使用的地址。与现实的缓存一样, 始终成立。
求处理全部 次请求所需的最少总时间。
输入格式
输入的第一行包含一个整数 (),表示测试数据组数。
每组数据的第一行包含五个整数 (,,,)。
第二行包含 个整数 (),依次表示每次请求访问的地址。
保证所有数据中 的和不超过 。
输出格式
对于每组数据,输出一行一个整数,表示最少总时间。
思路#
首先考虑朴素的 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 。
以上朴素做法复杂度为 ,代码实现如下:
void solve() {
...
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
vector<vector<ll>> ndp(m + 1, vector<ll>(m + 1, INF));
int cur = a[i];
for (int u = 0; u <= m; u++) {
for (int v = 0; v <= m; v++) {
ll d = dp[u][v];
ndp[u][v] = min(ndp[u][v], d + A);
if (cur != u && cur != v) {
ndp[v][cur] = min(ndp[v][cur], d + C);
} else if (cur == v) {
ndp[u][v] = min(ndp[u][v], d + B);
} else {
ndp[v][u] = min(ndp[v][u], d + B);
}
}
}
dp = ndp;
}
...
}cpp这里引入 ndp 是因为需要对 dp 中的原值反复访问,不能直接修改原 dp 。
接下来考虑优化:
先考虑缓存访问,注意到无论如何,缓存访问后第二位都是当前访问的元素。首先考虑缓存未击中情况下的缓存访问,对于任意的 (u,v) 执行一次未击中的缓存访问( ),变为 (v,x) ,若正在求解 (k,x) ,则只需要考虑所有 v=k 情况下的最小值即可,又由于 ,不必特别考虑 u=x 的情况,因为取最小值时不会影响答案。
又由于所有直接访问都会加上 A ,只需要考察当前方式相比全部直接访问多花的代价,那么考虑 x 时候只需要修改 v=x 的值,其他必定都是直接访问,不会改变值,可将复杂度降至 ,维护每列最小值即可。
代码#
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 509;
const ll INF = 1LL << 60;
void solve() {
int n, m, A, B, C;
cin >> n >> m >> A >> B >> C;
vector<vector<ll>> dp(m + 1, vector<ll>(m + 1, INF));
vector<int> a(n + 1);
vector<ll> minx(m + 1, INF);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dp[0][0] = 0;
minx[0] = 0;
for (int i = 1; i <= n; i++) {
int cur = a[i];
vector<ll> tmp(m + 1, INF);
for (int k = 0; k <= m; k++) {
if (k == cur)
continue;
tmp[k] = dp[k][cur];
if (dp[k][cur] != INF)
tmp[k] = min(tmp[k], dp[k][cur] + B - A);
if (dp[cur][k] != INF)
tmp[k] = min(tmp[k], dp[cur][k] + B - A);
if (minx[k] != INF)
tmp[k] = min(tmp[k], minx[k] + C - A);
}
for (int k = 0; k <= m; k++) {
if (k == cur)
continue;
dp[k][cur] = tmp[k];
minx[cur] = min(minx[cur], tmp[k]);
}
}
ll ans = INF;
for (int k = 0; k <= m; k++) {
ans = min(ans, minx[k]);
}
ll dlt = (ll)n * (ll)A;
cout << ans + dlt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
cpp