Description

我的一位亲密朋友 Loony 教授冲进了我的办公室。他满脸通红，看起来非常生气。他张口就说：“该死的手机制造商。我只是想发条短信，结果打一行字花了我十多分钟！”我试图安慰他：“到底怎么了？为什么花了你这么久？”他继续说道：“你难道没发现吗？！他们把字母排得一团糟？为什么 ‘s’ 是它所在按键的第 4 个字母？还有 ‘e’？为什么不是它所在按键的第一个字母？我得按 ‘7’ 四次才能打出一个 ‘s’？这太疯狂了！”

“冷静点，我的朋友，”我说，“这种方案已经用了很久了，甚至在短信发明之前就有了。他们不得不保持这种方式。”

“这不是借口，”他的脸越来越红。“是时候改变这一切了。一开始就是个愚蠢的主意。既然如此，为什么只在 8 个按键上放字母？为什么不用全部 12 个？为什么还必须是连续的？”

“呃……我……不知道……”我回答。

“好了，就这样。这些人显然不称职。我相信一定有人能想出更好的方案。”

我能看出来，他就是那种只会抱怨问题，却从不真正尝试解决问题的人。

在本题中，你需要设计一种最优的字母分配方案，使得输入一条消息所需的按键次数最少。你将得到可用按键数、每个按键最多可放的字母数、字母表的总字母数，以及每个字母在消息中出现的频率。字母可以任意分配到任意按键，顺序也可以任意。每个字母只能出现在一个按键上。字母表可能超过 26 个字母（不一定是英语）。

作为参考，目前手机键盘的布局如下：

按键 2：abc
按键 3：def
按键 4：ghi
按键 5：jkl
按键 6：mno
按键 7：pqrs
按键 8：tuv
按键 9：wxyz

第一次按某个按键会输入该键的第一个字母，每多按一次就输入下一个字母。例如，要输入单词 “snow”，你需要按 “7” 四次，再按 “6” 两次，再按 “6” 三次，最后按 “9” 一次。总共需要按键 10 次。

Input Format

输入文件的第一行包含测试用例数 $N$。接下来是 $N$ 个测试用例。每个用例包含两行。第一行有三个用空格分隔的整数，分别为每个按键最多可放的字母数 $P$、可用按键数 $K$、字母表中字母总数 $L$。第二行有 $L$ 个非负整数，分别表示每个字母在消息中出现的频率。第一个数字表示第一个字母出现的次数，第二个数字表示第二个字母出现的次数，依此类推。

Output Format

对于每个测试用例，输出如下格式：

Case #$x$: [最少按键次数]

表示在最优布局下输入消息所需的最少按键次数。

2
3 2 6
8 2 5 2 4 9
3 9 26
1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100

Case #1: 47
Case #2: 397

Hint

限制条件

• $P \times K \geq L$
• $0 \leq$ 每个字母的出现频率 $\leq 1000000$

小数据集（5 分，测试集 1 - 可见）

• $1 \leq N \leq 10$
• $1 \leq P \leq 10$
• $1 \leq K \leq 12$
• $1 \leq L \leq 100$

大数据集（10 分，测试集 2 - 隐藏）

• $1 \leq N \leq 100$
• $1 \leq P \leq 1000$
• $1 \leq K \leq 1000$
• $1 \leq L \leq 1000$

由 ChatGPT 4.1 翻译