Phân chia đội nhóm

Buổi 24 — Mock Contest Phase 1
Points
26
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ lập trình viên đánh số từ $1$ đến $N$. Độ tương hợp giữa hai người $i$ và $j$ là một số nguyên $S_{i,j}$ (có thể âm, và $S_{i,j} = S_{j,i}$, $S_{i,i} = 0$).

Bạn cần chia $N$ người này thành một số nhóm (số lượng nhóm tùy ý, mỗi người thuộc đúng một nhóm). Nếu hai người $i$ và $j$ ($i < j$) được xếp vào cùng một nhóm, tổng điểm tương hợp của cả đội sẽ được cộng thêm $S_{i,j}$.

Hãy tìm cách chia nhóm sao cho tổng điểm tương hợp là lớn nhất có thể.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 16$).
  • $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $S_{i,1}, S_{i,2}, \dots, S_{i,N}$ ($-10^9 \le S_{i,j} \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng điểm tương hợp lớn nhất.
Ví dụ
Input Output
3
0 10 -5
10 0 -5
-5 -5 0
10
4
0 -1 -1 -1
-1 0 -1 -1
-1 -1 0 -1
-1 -1 -1 0
0
Giới hạn
  • $1 \le N \le 16$.
  • $-10^9 \le S_{i,j} \le 10^9$, $S_{i,j} = S_{j,i}$, $S_{i,i} = 0$.
Draft saved