Editorial for Bedao Regular Contest 05 - FACTORY
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta sẽ phát biểu lại bài toán dưới dạng bài toán cái túi: Có ~n~ vật và mỗi vật có trọng lượng là ~t_i~, hãy chia các vật ra các túi sao cho trọng lượng của túi nặng nhất là nhỏ nhất
Giả sử đáp án của bài toán là ~max~.
Gọi ~F[mask]~ là số túi nhỏ nhất để chứa hết toàn bộ các con trong ~mask~ sao cho mỗi túi chỉ có trọng lượng tối đa là ~max~
~\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ F[mask] = min(F[submask]) + 1~
Với ~submask~ là phần ~xor~ hợp lệ của các ~mask~ con và ~mask~ (nghĩa là tổng trọng lượng của các con trong phần ~xor~ phải nhỏ hơn ~max~)
Vậy đáp án bài toán chính là ~max~ nhỏ nhất sao cho ~F[2^n - 1] \le k~
Độ phức tạp: ~O(3^n * log_2(sum(t_i)))~
Xem thêm về kĩ thuật duyệt ~mask~ con: all-submask
Comments