Ghép Cặp Nghiên Cứu
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ nhà nghiên cứu ($N$ chẵn, $N \le 16$) cần được chia thành $N/2$ cặp để thực hiện dự án. Nếu nhà nghiên cứu $i$ và $j$ được ghép cặp với nhau, mức độ ăn ý của cặp này là $w_{i, j}$.
Hãy tìm cách chia $N$ người thành $N/2$ cặp sao cho tổng mức độ ăn ý của tất cả các cặp là lớn nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên chẵn $N$ ($2 \le N \le 16$).
- $N$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên $w_{i, j}$ ($0 \le w_{i, j} \le 10^6$, $w_{i, j} = w_{j, i}$, $w_{i, i} = 0$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng mức độ ăn ý lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 0 3 1 5 3 0 6 2 1 6 0 4 5 2 4 0 |
11 |
Giới hạn
- $2 \le N \le 16$, $N$ chẵn
- $0 \le w_{i, j} \le 10^6$
Community Discussion