题目背景

题目描述

The term “Harvard architecture” applies to a computer that has physically separate memories for instructions and data. The term originated with the Harvard Mark I computer, delivered by IBM in 1944, which used paper tape for instructions and relays for data.

Some modern microcontrollers use the Harvard architecture – but not paper tape and relays! Data memory is organized in banks, each containing the same number of data items. Each data-referencing instruction has a byte offset $f$ to a bank, and a bit $a$ that is used to select the bank to be referenced. If $a$ is $0$, then bank $0$ is referenced. If $a$ is $1$, then the value in a bank select register (BSR) identifies the bank to be used. Assume each instruction takes the same time to execute, and there is an instruction that can set the BSR’s value.

For example, suppose there are $4$ banks of $8$ bytes each. To access location $5$, either use a single instruction with $a = 0$ and $f = 5$, or set the BSR to $0$ in one instruction and then use an instruction with $a = 1$ and $f = 5$. The first approach is faster since it does not require setting the BSR.

Now suppose (with the same memory) the location to access is $20$. Only one approach will work here: execute an instruction that sets the BSR to $2$ (unless the BSR already has the value $2$) and then use an instruction with $a = 1$ and $f = 4$.

A program is a sequence of operations. Each operation is either

• a variable reference, written as V$i$, where $i$ is a positive integer, or
• a repetition, written as R$n$ <program> E, where $n$ is a positive integer and <program> is an arbitrary program. This operation is equivalent to n sequential occurrences of <program>.

Your problem is to determine the minimum running time of programs. In particular, given the number and size of the memory banks and a program to be executed, find the minimum number of instructions (which reference memory location and possibly set the BSR) that must be executed to run the program. To do this you must identify a mapping of variables to memory banks that yields the smallest execution time, and report that execution time – that is, the number of memory references and BSR register settings required. The BSR’s value is initially undefined, and changes only when an instruction explicitly sets its value.

输入格式

The input consists of a single test case. A test case consists of two lines. The first line contains two integers $b$ and $s$, where $1 \leq b \leq 13$ is the number of memory banks and $1 \leq s \leq 13$ is the number of variables that can be stored in each memory bank. The second line contains a non-empty program with at most $1 000$ space-separated elements (each R$n$, V$i$, and E counts as one element).

You may assume the following:

• In a repetition R$n$, the number of repetitions satisfies $1 \leq n \leq 10^6$.
• In a loop operation R$n$ <program> E, the loop body <program> is not empty.
• In a variable reference V$i$, the variable index satisfies $1 \leq i \leq \min(b \times s, 13)$.
• The total number of variable references performed by an execution of the program is at most $10^{12}$.

输出格式

Display the minimum number of instructions that must be executed to complete the program.

题目大意

【题目描述】

“哈佛架构”一词适用于指令和数据具有物理上分开的存储器的计算机。该术语起源于哈佛 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$ <program> E，其中 $n$ 是正整数，<program> 是任意程序。此操作相当于 <program> 的 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$ <program> E 中，循环体 <program> 不为空。
• 在变量引用 V$i$ 中，变量索引满足 $1 \leq i \leq \min(b \times s, 13)$。
• 程序执行的总变量引用数最多为 $10^{12}$。

【输出格式】

显示完成程序所需执行的最小指令数。

翻译来自于：ChatGPT。

1 2
V1 V2 V1 V1 V2

5

2 1
V1 V2 V1 V1 V2

6

1 2
R10 V1 V2 V1 E

30

4 1
V1 R2 V2 V4 R2 V1 E V3 E

17