P13463 [GCJ 2008 #1C] Text Messaging Outrage

我的一位亲密朋友 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 次。

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

对于每个测试用例，输出如下格式： Case #$x$: [最少按键次数] 表示在最优布局下输入消息所需的最少按键次数。

**限制条件** - $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 翻译