最佳置换算法opt（optimal）c++源码

以下是最佳置换算法opt（optimal）的C++源码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010;

int n, m, a[N], b[N], pos[N], f[N][3], ans;

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        b[a[i]] = i;
    }

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1; i <= m; i ++ )
    {
        int x;
        cin >> x;
        int j = b[x];
        pos[i] = j;

        if (f[i - 1][0] != 0x3f3f3f3f) f[i][0] = f[i - 1][0] + (j > pos[i - 1]);
        if (f[i - 1][1] != 0x3f3f3f3f) f[i][1] = f[i - 1][1] + (j > pos[f[i - 1][0]]);
        if (f[i - 1][2] != 0x3f3f3f3f) f[i][2] = f[i - 1][2] + (j > pos[f[i - 1][1]]);

        f[i][0] = min(f[i][0], min(f[i][1], f[i][2]));
        f[i][2] = min(f[i][2], min(f[i][0] - 1, f[i][1] - 1));
        f[i][1] = min(f[i][1], min(f[i][0] - 1, f[i][2] - 1));
        ans += f[i][2];
    }

    cout << ans << endl;

    return 0;
}

其中，变量n表示有n个页面，m表示有m个内存块，a[i]表示第i个访问的页面号，b[i]表示页面号为i的位置，pos[i]表示第i个内存块中页面的位置，f[i][j]表示前i个内存块中，第i个内存块为j时的最小缺页数。