7968: BZOJ3968：[WF2013]Harvard

“哈佛结构”是指一台拥有多个分散内存用于记录指令与数据的计算机。这个术语起源于“哈佛马克1号”计算机。它由IBM于1944年制造，用纸带记录指令，用继电器来储存数据。 一些最新的单片机使用了“哈佛结构”（当然没有用纸带和继电器）。数据是由“内存库”来组织，每个“内存库”拥有相同数量的数据。每一个访问数据的指令都由2个数控制。一个数a（非0即1）。如果a为0，那么访问的是0号“内存库”。如果a为1则访问BSR（bank select register “内存库”选择寄存器）中选择的“内存库”。另一个数f表示访问该“内存库”的第f个变量。我们假设每一个指令花费相同的时间运行。另外还有一个可以设定BSR值的命令。 举例来说，假设有4个“内存库”，每个“内存库”有8个字节。为了访问位置5（0号“内存库”第5个变量），我们有两种方法。第一种，使用指令a=0，f=5。第二种，先将BSR的值设为0，然后使用指令a=1，f=5。第一种方法更快，因为它不需要花费时间设置BSR。 现在假设（还是刚才的“内存库”）我们要访问位置20（2号“内存库”第4个变量）。现在只有1种方法能够访问。将BSR的值设为2（除非BSR原来就是2），然后用指令a=1，f=4。 一个程序是一个操作的序列，每个操作是： ●一个变量访问操作，写作Vi，i是一个正整数。 ●一个循环操作，写作 Rn <program> E，n是一个正整数，<program>是一个任意的程序。这个操作等价于依次执行n遍<program>。 你的工作是决定一个程序最小的运行时间。更确切的说，给出“内存库”的个数和大小，需要执行的程序，输出为了执行这个程序最小的指令数（包括数据访问指令和设定BSR的指令）。为了完成这个，你必须设定一个变量到“内存库”的映射，使得这个程序运行时间最短，并且输出这个时间（也就是程序运行的指令数）。开始的时候BSR的值为undefined，直到一条命令显式的设定了它的值。

输入格式

每组输入包含一个case，两行。第一行两个整数b和s，1≤b≤13代表“内存库”的个数，1≤s≤13代表每个“内存库”的大小（即能储存的变量数）。第二行是一个非空程序，最多有1000个元素（每个Rn，Vi，E都算1个元素）。 保证： 在循环Rn中，循环次数1≤n≤10^6。 在循环Rn <program> E中, <program>非空。 在数据访问Vi中，1≤i≤min(b*s,13)。 程序访问变量的次数不超过10^12次。

输出格式

输出运行该程序最少需要的指令数。

样例输入

1 2
V1 V2 V1 V1 V2

样例输出

5

提示

没有写明提示

题目来源

没有写明来源