Chia Ba Phần

Lời giải: Chia Kiện Rơm

Hướng tiếp cận

Dùng quy hoạch động (DP) để duyệt tất cả cách chia $N$ vật vào 3 nhóm. Trạng thái DP theo dõi tổng của nhóm 2 và nhóm 3; tổng nhóm 1 suy ra từ tổng cả ba.

Nhận xét quan trọng

1. Với $N\le 20$ và $S_i\le 100$, tổng tối đa là $20\times 100=2000$. Không gian trạng thái $(b_2,b_3)$ chỉ là $2001\times 2001\approx 4\times {10}^6$ — chấp nhận được.
2. Không cần lưu $b_1$ vì $b_1=\text{total}-b_2-b_3$.
3. Dùng hai mảng boolean luân phiên (rolling array) để tiết kiệm bộ nhớ: good[cur][b2][b3] = có thể đạt trạng thái $(b_2,b_3)$ sau khi xử lý các vật đầu.

Thuật toán

1. Tính total = S_1 + S_2 + ... + S_N.
2. Khởi tạo good[0][0][0] = true.
3. Với mỗi vật $i$ (từ 0 đến $N-1$): với mỗi trạng thái (b2, b3) hợp lệ hiện tại, lan chuyển sang:
   • Đặt vào nhóm 1: (b2, b3) giữ nguyên.
   • Đặt vào nhóm 2: (b2 + S_i, b3).
   • Đặt vào nhóm 3: (b2, b3 + S_i).
4. Sau khi xử lý hết, duyệt tất cả trạng thái (b2, b3) hợp lệ, tính b1 = total - b2 - b3, cập nhật đáp án = $min(max(b_1,b_2,b_3))$.

Độ phức tạp

• Thời gian: $O(N·{\text{total}}^2)$ với $\text{total}\le 2000$
• Bộ nhớ: $O({\text{total}}^2)$