Thi Đấu Mười Môn

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\le 20$, ta dùng DP bitmask.

Nhận xét quan trọng

1. 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.
2. 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$.
3. Trạng thái DP: $dp[mask]$ = tổng điểm tối đa khi đã phân các thí sinh trong $mask$ vào $|mask|$ môn đầu tiên ($|mask|$ = popcount).

Thuật toán

1. Khởi tạo $dp[0]=0$, còn lại $=-\infty$.
2. Duyệt mọi $mask$ từ $0$ đến $2^N-1$:
   • Đặt $k=popcount(mask)$ (số môn đã phân).
   • Với mỗi thí sinh $i$ chưa dùng ($i\notin mask$):
     • Thí sinh $i$ thi môn $k+1$, được $s_{i,k+1}$ điểm.
     • $mas{k}^{\prime }=mask|(1\ll i)$.
     • $score=dp[mask]+s_{i,k+1}$.
     • Kiểm tra bonus: với mỗi bonus có $K_j=k+1$, nếu $score\ge P_j$ thì .
     • Cập nhật $dp[mas{k}^{\prime }]=max(dp[mas{k}^{\prime }],score)$.
3. Đáp án: $dp[(1\ll N)-1]$.

Độ phức tạp

• Thời gian: $O(2^N·N·B)$
• Bộ nhớ: $O(2^N)$

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