| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P167PROF - ROUND 7F - Trò chơi trên bảng |
Cho bảng số A gồm n hàng và n cột. Các hàng được đánh số từ 1 đến n, từ trên xuống dưới, các cột của lưới được đánh số từ 1 đến n, từ trái sang phải. Ô giao của hàng i và cột j gọi là ô (i, j) và được điền một số nguyên aij có giá trị tuyệt đối không vượt quá 109.
Xét trò chơi đối kháng giữa hai người trên bảng như sau: Trò chơi diễn ra trong n lượt đi, mỗi lượt người thứ nhất chọn một hàng, người thứ hai chọn một cột. Giả sử, tại một lượt đi, nếu người chơi thứ nhất chọn hàng i, người chơi thứ hai chọn cột j, khi đó người thứ nhất được cộng aij điểm, người thứ hai được cộng -aij điểm. Sau lượt đi đó, bảng bị xóa hàng và cột mà hai người chơi vừa chọn. Người có điểm càng cao càng thể hiện sự thông minh của mình.
Yêu cầu: Cho bảng số A và biết cả hai người đều chơi tối ưu, hãy tính điểm lớn nhất mà người thứ nhất có thể đạt được.
Input
Dòng đầu tiên ghi K là số bộ test. Tiếp theo là K nhóm dòng, mỗi nhóm là một bộ test có cấu trúc như sau:
- Dòng đầu của nhóm ghi số n (n ≤ 16);
- n dòng sau, mỗi dòng chứa n số nguyên mô tả bảng số.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output
Gồm K dòng, mỗi dòng một số nguyên là điểm lớn nhất có thể của người thứ nhất tương ứng với dữ liệu vào.
Example
Input:
3
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10
Output:
5
5
-10
| Được gửi lên bởi: | adm |
| Ngày: | 2016-04-10 |
| Thời gian chạy: | 1s-3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
