Hướng dẫn giải của Thi Đấu Mười Môn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Thi Đấu Mười Môn

Hướng tiếp cận

Bài toán yêu cầu phân $N$ thí sinh vào $N$ môn thi (hoán vị) sao cho tổng điểm + thưởng lớn nhất. Với $N \leq 20$ , ta dùng DP bitmask.

Nhận xét quan trọng

Xét phân công từng môn thi theo thứ tự $1, 2, \dots, N$ . Khi phân xong $k$ môn đầu, ta biết tập thí sinh đã được chọn (bitmask) và tổng điểm $k$ môn đầu.
Phần thưởng chỉ phụ thuộc vào tổng điểm $K_{i}$ môn đầu tiên. Khi ta vừa phân xong môn $k$ , ta kiểm tra các bonus có $K_{i} = k$ .
Trạng thái DP: $d p [m a s k]$ = tổng điểm tối đa khi đã phân các thí sinh trong $m a s k$ vào $| m a s k |$ môn đầu tiên ( $| m a s k |$ = popcount).

Thuật toán

Khởi tạo $d p [0] = 0$ , còn lại $= - \infty$ .
Duyệt mọi mask từ 0 đến 2N−1:
- Đặt $k = p o p c o u n t (m a s k)$ (số môn đã phân).
- Với mỗi thí sinh i chưa dùng (i∉mask):
  - Thí sinh $i$ thi môn $k + 1$ , được $s_{i, k + 1}$ điểm.
  - $m a s k^{'} = m a s k | (1 ≪ i)$ .
  - $s c o r e = d p [m a s k] + s_{i, k + 1}$ .
  - Kiểm tra bonus: với mỗi bonus có $K_{j} = k + 1$ , nếu $s c o r e \geq P_{j}$ thì $s c o r e + = A_{j}$ .
  - Cập nhật $d p [m a s k^{'}] = max (d p [m a s k^{'}], s c o r e)$ .
Đáp án: $d p [(1 ≪ N) - 1]$ .

Độ phức tạp

Thời gian: $O (2^{N} \cdot N \cdot B)$
Bộ nhớ: $O (2^{N})$

Với $N = 20$ : $2^{20} \cdot 20 \cdot 20 \approx 4 \cdot 10^{8}$ — vừa đủ trong 2 giây với C++.

Bình luận

Không có bình luận tại thời điểm này.