← 返回题目列表

AtCoder · utpc2011_8

H. 缓存策略

中文机器翻译题面 查看原题

现在,G○○gle Code Jam的地区赛即将开始。坐在斜前右方的男人的ID似乎叫lyrically。我记得在东京大学时代,有个ID相似的伙伴,但我的伙伴应该一个不剩全都是美少女。

在我记忆中的lyrically,不仅算法能力和实现能力出色,还以靠气势解题而闻名。例如,即使程序的计算复杂度稍差,也能通过巧妙的实现使其高速运行,并使之成为正确解,这也是他擅长的。

在提高程序运行速度方面,非常重要的是与缓存内存的相性。

問題

考虑每个块的读取成本不同的内存。 在已知所有将发生的内存访问的情况下, 我们想要找出全相联缓存中最优的缓存策略。 以下,用简单的语言来说明。

M 个箱子, 有N 个球。 球有 1 减去 N , 每个球 i 都有确定的重量 wi 。 另外,长度 K 序列 使用 a1, a2, …, aK 被给予。 每个 aj 是 您也可以写 1 ≤ aj ≤ N 都是满足条件的整数。

起初所有的箱子都是空的。 j = 1, 2, …, K 的顺序,想进行以下操作。 如果有

  • 球 aj 放入的箱子,则不进行任何操作。
    • 这项操作的成本为 0。 如果没有
  • 球 aj 放入的箱子,则将球放入任意一个箱子 aj 。
    • 把球放进盒子时,如果盒子里已经有球,就把它带到外面。
    • 这次手术的费用是 waj (费用不取决于你放入的盒子或取出的球。)

创建一个程序来计算最小成本总额。

入力

输入的第一行包含三个整数。 M, N, K 。

继续 N 线 i 行是一个整数 wi 被写下了。

继续 K 线 j 行是一个整数 aj 被写下了。

出力

输出成本的最低总和。

制約

  • 1 ≤ M ≤ 10
  • 1 ≤ N ≤ 104
  • 1 ≤ K ≤ 104
  • 1 ≤ wi ≤ 104
  • 1 ≤ aj ≤ N

部分点

针对该问题的判断设置了一组20分的测试用例。 该组中包含的测试用例的输入满足以下条件。

  • 1 ≤ M ≤ 3
  • 1 ≤ N ≤ 10
  • 1 ≤ K ≤ 103

入出力例

入力例 1

入力例 1:

3 3 6
10
20
30
1
2
3
1
2
3

输入示例 1 的输出示例:

60

入力例 2

入力例 2:

2 3 6
10
20
30
1
2
3
1
2
3

输入示例 2 的输出示例:

80