Editorial for Bedao Regular Contest 05 - FACTORY


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.