Hướng dẫn giải của Sắc Lệnh Giáo Dục

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

Hướng tiếp cận

Bài toán yêu cầu chọn $d$ hoạt động để bảo vệ nhằm tối đa hóa tổng giá trị học sinh an toàn. Ta đổi góc nhìn: thay vì chọn $d$ hoạt động bảo vệ, ta chọn $b = k - d$ hoạt động bị cấm, và tối thiểu hóa tổng giá trị học sinh bị đình chỉ.

Một học sinh bị đình chỉ khi và chỉ khi tập hoạt động của họ là tập con của tập bị cấm. Bài toán trở thành: chọn tập $B$ có $b$ phần tử sao cho $\sum_{i : A_{i} \subseteq B} v_{i}$ là nhỏ nhất.

Nhận xét quan trọng

Biểu diễn bitmask: Với $k \leq 20$ , mỗi tập hoạt động có thể biểu diễn bằng một bitmask. Tập hợp tất cả $2^{k}$ bitmask có thể được duyệt qua.
Tổng trên tập con (Sum Over Subsets — SOS): Gọi $f [mask]$ là tổng giá trị của tất cả học sinh có tập hoạt động đúng bằng $mask$ . Ta cần tính $g [mask] = \sum_{s \subseteq mask} f [s]$ — tổng giá trị các học sinh mà tập hoạt động là tập con của $mask$ .
SOS DP: Phép biến đổi trên có thể tính trong $O (k \cdot 2^{k})$ bằng kỹ thuật SOS DP (tương tự biến đổi Zeta trên poset tập con).
Đáp án: Duyệt qua tất cả mask $B$ có $popcount (B) = b = k - d$ phần tử, tìm $B$ cho $g [B]$ nhỏ nhất. Kết quả là $total - min g [B]$ .

Thuật toán

Đọc input, tính $f [mask]$ cho mỗi bitmask (gộp giá trị các học sinh có cùng tập hoạt động).

Tính SOS DP:

g = copy of f
for bit = 0 to k-1:
    for mask = 0 to 2^k - 1:
        if mask has bit set:
            g[mask] += g[mask XOR (1 << bit)]

Sau bước này, $g [mask]$ chứa tổng $f [s]$ với mọi $s \subseteq mask$ .

Duyệt tất cả mask $B$ có đúng $k - d$ bit 1, tìm $min g [B]$ .
In ra $total - min g [B]$ .

Độ phức tạp

Thời gian: $O (n + k \cdot 2^{k})$ . Với $k = 20$ , ta có $20 \times 2^{20} \approx 2 \times 10^{7}$ phép tính cho SOS DP, cộng thêm $2^{20} \approx 10^{6}$ cho bước duyệt cuối.
Bộ nhớ: $O (2^{k} + n)$ . Mảng $f$ và $g$ có kích thước $2^{k}$ .

Bình luận

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