分数: 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