警告
在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。
问题陈述
您正在编写一个程序,该程序可以最佳地划分 N 贵公司员工,员工 1, \ldots, N,最多分为三组。
对于所有员工对 i, j (1 \leq i < j \leq N),人工智能已经计算出幸福感 如果这两名员工属于同一组,就会出现 A_{i,j} (不一定是正数)。
设分组的合意性为 A_{i,j} 所有对员工 i, j 属于同一组(如果不存在这样的对,则可取性为 0)。找出分组的最大可能的期望值。
约束
- 2 \leq N \leq 10
- -10^6 \leq A_{i,j} \leq 10^6
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
a_{1,2} a_{1,3} \ldots a_{1, N}
a_{2,3} a_{2,4} \ldots a_{2, N}
:
a_{N-1,N}
输出
打印分组的最大可能期望值。
示例输入 1
6 10 10 -10 -10 -10 10 -10 -10 -10 -10 -10 -10 10 -10 -10
示例输出 1
40
考虑创建以下三个组:包含 Employee 的组 1, 2,3,一个包含 Employee 的组 4, 5,以及 Employee 组 6。有四对员工属于同一组: (1,2), (1,3), (2,3), (4,5),为了满足 A_{1,2} + A_{1,3} + A_{2,3} + A_{4,5} = 10 + 10 + 10 + 10 = 40。这是最优分组。
示例输入 2
3 1 1 1
示例输出 2
3
所有员工可能属于同一组。