P10619 [ICPC 2013 WF] Harvard


“哈佛架构”一词适用于指令和数据具有物理上分开的存储器的计算机。该术语起源于哈佛 Mark I 计算机，由 IBM 于 1944 年交付，该计算机使用纸带作为指令，使用继电器作为数据。 一些现代微控制器使用哈佛架构——但不使用纸带和继电器！数据存储器被组织成多个存储区（bank），每个存储区包含相同数量的数据项。每条引用数据的指令都有一个字节偏移量 $f$ 和一个位 $a$，用于选择要引用的存储区。如果 $a$ 为 $0$，则引用存储区 $0$。如果 $a$ 为 $1$，则在*存储区选择寄存器*（BSR）中的值标识要使用的存储区。假设每条指令执行时间相同，并且存在可以设置 BSR 值的指令。 例如，假设有 $4$ 个存储区，每个存储区有 $8$ 个字节。要访问位置 $5$，可以使用 $a = 0$ 和 $f = 5$ 的单条指令，或者在一条指令中将 BSR 设置为 $0$，然后使用 $a = 1$ 和 $f = 5$ 的指令。第一种方法更快，因为它不需要设置 BSR。 现在假设（使用相同的存储器）要访问的位置是 $20$。这里只能使用一种方法：执行一条指令将 BSR 设置为 $2$（除非 BSR 已经是 $2$），然后使用 $a = 1$ 和 $f = 4$ 的指令。 程序是操作的序列。每个操作可以是 - 变量引用，写作 V$i$，其中 $i$ 是正整数，或 - 重复，写作 R$n$ `` E，其中 $n$ 是正整数，`` 是任意程序。此操作相当于 `` 的 n 次连续出现。 你的任务是确定程序的最小运行时间。具体来说，给定内存存储区的数量和大小以及要执行的程序，找出必须执行的最小指令数（引用内存位置和可能设置 BSR），以运行程序。为此，你必须确定将变量映射到存储区的方式，以产生最小的执行时间，并报告该执行时间——即完成程序所需的内存引用和 BSR 寄存器设置的数量。BSR 的值最初未定义，仅在指令显式设置其值时更改。

输入包含一个测试用例。测试用例包含两行。第一行包含两个整数 $b$ 和 $s$，其中 $1 \leq b \leq 13$ 是存储区的数量，$1 \leq s \leq 13$ 是每个存储区可以存储的变量数。第二行包含一个非空程序，最多包含 $1 000$ 个用空格分隔的元素（每个 R$n$, V$i$ 和 E 都算作一个元素）。 你可以假设以下几点： - 在重复 R$n$ 中，重复次数满足 $1 \leq n \leq 10^6$。 - 在循环操作 R$n$ `` E 中，循环体 `` 不为空。 - 在变量引用 V$i$ 中，变量索引满足 $1 \leq i \leq \min(b \times s, 13)$。 - 程序执行的总变量引用数最多为 $10^{12}$。

显示完成程序所需执行的最小指令数。 翻译来自于：[ChatGPT](https://chatgpt.com/)。