Editorial for Bedao Mini Contest 13 - SOCCER
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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