AT_past201912_g.組分け

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

有 $n$ 个人，编号 $1$ 到 $n$ 。现在要把他们分成至多三组。

对于每个满足 $1\le i\lt j\le n$ 的整数对 $(i,j)$ ，都会有一个整数 $a_{i,j}$ 表示 $i$ 和 $j$ 被分在一组时产生的“幸福指数”。若出现一个人独立成组的情况，那么他所产生的“幸福指数”为 $0$ 。

请求出“幸福指数”的最大和。

第一行：一个整数 $n$ 。

第二行至第 $n$ 行：第 $(i+1)$ 行第 $(j-1)$ 列输入整数 $a_{i,j}$ 。

一行一个整数，“幸福指数”最大和。

输入#1

6
10 10 -10 -10 -10
10 -10 -10 -10
-10 -10 -10
10 -10
-10

输出#1

让 $1,2,3$ 一组， $4,5$ 一组， $6$ 一组，则“幸福指数”最大和为 $a_{1,2}+a_{1,3}+a_{2,3}+a_{4,5}=10+10+10+10=40$ 。

所有员工在同一组里。

$2\le n\le 10$ ， $-10^6\le a_{i,j}\le 10^6$ 。

输入解题思路，AI测评打分。不知道怎么写?