Editorial for Bedao Mini Contest 13 - SOCCER


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 coi mỗi học sinh là một nút trong đồ thị và các mối quan hệ bạn bè là cạnh của đồ thị

Subtask 1

Ta sẽ sinh nhị phân để chia các học sinh thành 2 bên và tính tổng sức mạnh.

Subtask 2

Nhận xét: Độ chênh lệch sức mạnh giữa 2 nhóm bằng độ chênh lệch tổng bậc ở các nút chia ~2~

Giải thích: nếu một cạnh có giá trị là ~v~ nằm ở một nhóm thì tổng bâc ở nhóm đó được cộng thêm ~2v~, ngược lại nếu cạnh đó nối với 2 đỉnh ở 2 nhóm khác nhau thì tổng bậc ở mỗi nhóm sẽ được tăng thêm ~v~ và chênh lệch không hề thay đổi.

Vậy ta có công thức quy hoạch động ~dp[i][cnt][sum] = true/false~ tức là xét đến học sinh thứ ~i~ và đã lựa chọn ~cnt~ học sinh vào nhóm 1 trong số các học sinh từ ~1 \rightarrow i - 1~ và tổng bậc của nhóm 1 là ~sum~.

Cách chuyển trạng thái giống như bài toán quy hoạch động cái túi cơ bản nên xin nhường lại cho bạn đọc.

Độ phức tap: ~\mathcal{O}(n^4)~

Subtask 3

Hàm quy hoạch động của ta có thể dùng bitset để chuyển trạng thái nhanh hơn. Cụ thể các bạn có thể đọc comment này trên codeforces.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.