← 返回题目列表

AtCoder · awc0010_e

E. 展会展位安排

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

分数: 433 分

问题陈述

高桥负责组织一个展览,其中 N 公司正在参展。会场有 N 展位排列成圆圈,编号 1 to N 按顺时针顺序。由于展位呈圆形布置 k 及展位 k+1 (1 \leq k \leq N-1)相邻,且摊位 N 及展位 1 也相邻。因此,正好有 N 对相邻的展位。

的 N 公司也编号 1 to N,最初,公司 i 放置在展位上 i (1 \leq i \leq N)。每个展位恰好包含一个公司,并且每个公司仅使用一个展位。

在展会上,对于每对相邻的展位,两家公司将举办一场合作活动。公司时的观众吸引效应 i 和公司 j 协作表示为 C_{i,j} (C_{i,j} = C_{j,i}).

Takahashi 可以执行以下操作 0 或更多次,最多 K 次:选择两家不同的公司并交换他们当前使用的展位。每次操作选择哪两家公司没有限制;一个公司可能会在多次操作中被选择,并且同一对公司可能会被多次选择。

考虑所有操作完成后的安排。让 p_k 表示展位上的公司 k 操作后。然后 (p_1, p_2, \ldots, p_N) 是一个排列 (1, 2, \ldots, N)。总体吸引观众效果 N 对相邻展位是

$\sum_{k=1}^{N-1} C_{p_k, p_{k+1}} + C_{p_N, p_1}$

找到最佳选择操作时该总数的最大值。

约束

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

输入

N K
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}
  • 第一行包含两个空格分隔的整数: N、企业及展位数量,以及 K,最大操作数。
  • 以下 N 行包含 N \times N 矩阵 C 代表观众吸引效果。的 i这些行中的第 (1 \leq i \leq N) 包含空格分隔的值 C_{i,1}, C_{i,2}, \ldots, C_{i,N},代表公司之间的受众吸引效果 i 和对方公司。
  • 保证 C_{i,j} = C_{j,i} 和 C_{i,i} = 0.

输出

在一行上打印表演后所有相邻展位对所能达到的最大总观众吸引效果 0 或更多且最多 K 操作。


示例输入 1

3 0
0 10 30
10 0 20
30 20 0

示例输出 1

60

示例输入 2

4 1
0 5 50 100
5 0 5 100
50 5 0 50
100 100 50 0

示例输出 2

255

示例输入 3

6 3
0 10 80 50 30 100
10 0 90 20 70 40
80 90 0 60 10 50
50 20 60 0 100 30
30 70 10 100 0 80
100 40 50 30 80 0

示例输出 3

470