33OJ
登录 注册

#P17643. [ICPC 2019 Yinchuan R] Xian Xiang

[ICPC 2019 Yinchuan R] Xian Xiang

题目描述

最近几天,Raven 迷上了一款名为“仙乡”的游戏。

游戏开始时,在一个 n×mn \times m 的矩形区域中散布着一些物品。每个物品拥有 kk 种属性。玩家可以通过一条折线连接任意两个物品来消除它们,该折线的每一段必须是水平或垂直的。然而,这条折线最多只能改变一次方向,且路径上不能有任何物品(该规则类似于“连连看”)。每当物品被消除后,这些物品所在的格子将变为空白,并且会根据被消除的两个物品匹配的属性数目给予一定分数。若两物品间有 00 个公共属性,得分为 s0s_0;若有 11 个公共属性,得分为 s1s_1,……;若有 pp 个公共属性,得分为 sps_p。

游戏中有一个记分牌,Raven 迫切地想要登上记分牌的顶端。因此他必须尽己所能获得游戏中的最高分。

输入格式

第一行是一个整数 T (1≤T≤20)T~(1 \le T \le 20),表示测试数据的组数。

每组数据起始于三个正整数 n,m,k (1≤n,m≤7,1≤k≤5)n, m, k~(1 \le n, m \le 7, 1 \le k \le 5),分别表示矩形区域的长、宽和每个物品的属性种数。

接下来是 n×mn \times m 个长度为 kk 的字符串,表示对应的物品。初始时,若格子为空,则该字符串由 kk 个 "-" 组成;若格子中有物品,则该字符串由 kk 个小写字母组成。每个小写字母代表一种属性。如果相连的两个物品在字符串的相同位置上的字母相同,则表明这两个物品在该位置具有相同的属性。

最后一行是 k+1k+1 个正整数 s0,s1,⋯ ,sk (1≤si≤10000)s_0, s_1, \cdots, s_k~(1 \le s_i \le 10000)。

保证每组数据中的物品数量为偶数且不超过 1818。

输出格式

对于每组数据,在一行中输出一个整数,表示该局游戏可得的最高可能分数。

3
2 2 3
aaa aaa
bbb bbb
1 10 100 1000 
2 3 3
aaa --- bbb
bbb --- aaa
1 10 100 1000 
1 4 3
aaa bba abb aaa 
1 10 100 1000
2000 
2 
1010

提示

在第一个样例中,消除第一行和第二行中的两对物品,你将获得 20002000 分。

在第二个样例中,由于相同物品无法相连,你只能获得 22 分。

在第三个样例中,先消除中间的两个物品,再消除最左端和最右端的两个物品。

翻译由 DeepSeek V4 Pro 完成