← 返回题目列表

AtCoder · awc0083_e

E. 宝石项链

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

分数: 433 分

问题陈述

高桥决定准确选择 K 珠宝来自 N 在珠宝店购买珠宝制作项链。珠宝编号为 1 to N,并且每个都只有一个。同一宝石不能被选择多次。

每颗宝石 i (1 \leq i \leq N) 有一个称为“亮度”的整数值 P_i。另外,还有一个整数值 C_{i,j} 代表“和谐”时的宝石 i 和宝石 j 彼此相邻放置。和谐对称、令人满意 C_{i,j} = C_{j,i}.

由于项链是圆形的,因此选择 K 珠宝排列成环形。排列方式可以自由选择。项链的“美度”计算为以下两个值的总和:

  • 每个的亮度总和 K 精选珠宝
  • 项链上所有相邻宝石对的和谐度之和(恰好有 K 之间的相邻对 K 排列成戒指的珠宝)

例如,如果 K = 3 和珠宝 a, b, c 按照这个顺序排列成一个环,美丽的是 P_a + P_b + P_c + C_{a,b} + C_{b,c} + C_{c,a}.

高桥希望最大限度地发挥项链的美感。准确选择 K 珠宝来自 N 宝石并以最佳循环顺序排列它们。寻找美的最大价值。

请注意,因为 C_{i,j} = C_{j,i},通过旋转或反射重合的圆形排列具有相同的美感。因此,求最大值时无需区分它们。

约束

  • 3 \leq K \leq N \leq 16
  • -10^6 \leq P_i \leq 10^6 (1 \leq i \leq N)
  • -10^6 \leq C_{i,j} \leq 10^6 (1 \leq i, j \leq N)
  • C_{i,j} = C_{j,i} (1 \leq i, j \leq N)
  • C_{i,i} = 0 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N K
P_1 P_2 \ldots P_N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
:
C_{N,1} C_{N,2} \ldots C_{N,N}
  • 第一行包含两个用空格分隔的整数: N,珠宝数量,以及 K,要选择的宝石数量。
  • 第二行包含亮度值 P_1, P_2, \ldots, P_N 以空格分隔。
  • 以下 N 行(来自行 3 转线 N + 2) 给出 N \times N 表示和声值的矩阵。
  • 的 (2 + i)第行 (1 \leq i \leq N) 包含 C_{i,1}, C_{i,2}, \ldots, C_{i,N} 以空格分隔。

输出

单行输出项链美感的最大值。


示例输入 1

4 3
10 20 30 40
0 5 3 1
5 0 8 2
3 8 0 6
1 2 6 0

示例输出 1

106

示例输入 2

5 3
-10 -20 -30 -40 -50
0 -5 -3 -1 -2
-5 0 -8 -2 -4
-3 -8 0 -6 -1
-1 -2 -6 0 -3
-2 -4 -1 -3 0

示例输出 2

-76

示例输入 3

8 5
100 200 150 300 250 50 175 225
0 10 20 30 15 5 25 35
10 0 40 10 20 30 15 5
20 40 0 50 10 20 30 10
30 10 50 0 60 15 25 20
15 20 10 60 0 35 45 30
5 30 20 15 35 0 10 40
25 15 30 25 45 10 0 55
35 5 10 20 30 40 55 0

示例输出 3

1325

示例输入 4

12 8
500 -300 400 100 -200 600 350 -150 450 200 -100 300
0 50 -30 20 10 -40 60 15 -25 35 45 -10
50 0 40 -20 30 15 -35 25 50 -15 20 10
-30 40 0 55 -10 20 30 -45 15 25 -20 35
20 -20 55 0 45 -30 10 40 -15 50 30 -25
10 30 -10 45 0 25 -20 35 40 -30 15 50
-40 15 20 -30 25 0 50 -10 30 45 -35 20
60 -35 30 10 -20 50 0 40 -15 25 35 -30
15 25 -45 40 35 -10 40 0 50 -20 30 15
-25 50 15 -15 40 30 -15 50 0 45 -10 25
35 -15 25 50 -30 45 25 -20 45 0 40 -35
45 20 -20 30 15 -35 35 30 -10 40 0 50
-10 10 35 -25 50 20 -30 15 25 -35 50 0

示例输出 4

3240

示例输入 5

3 3
1000000 1000000 1000000
0 1000000 1000000
1000000 0 1000000
1000000 1000000 0

示例输出 5

6000000