Hướng dẫn giải của Chia Ba Phần

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

Với $N \leq 20$ và $S_{i} \leq 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.
Không cần lưu $b_{1}$ vì $b_{1} = total - b_{2} - b_{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

Tính total = S_1 + S_2 + ... + S_N.
Khởi tạo good[0][0][0] = true.
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).
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 \cdot {total}^{2})$ với $total \leq 2000$
Bộ nhớ: $O ({total}^{2})$

Bình luận

Không có bình luận tại thời điểm này.