1. Phân tích bài toán
- Đây là bài toán tối ưu hóa việc kết hợp các phần tử liên tiếp, tương tự như bài toán Nhân ma trận liên tiếp hoặc Cây nhị phân tìm kiếm tối ưu.
- Điểm quan trọng: Màu của một hỗn hợp sau khi trộn nhiều thành phần từ chỉ số đến luôn bằng:
Điều này có nghĩa là dù bạn trộn theo thứ tự nào trong đoạn , màu cuối cùng của đoạn đó vẫn không thay đổi.
2. Ý tưởng thuật toán (Quy hoạch động)
Ta gọi là lượng khói tối thiểu để trộn các hỗn hợp từ vị trí đến vị trí .
- Trạng thái cơ bản: Nếu , (một hỗn hợp duy nhất không tạo ra khói).
- Công thức truy hồi: Để tính , ta thử chia đoạn thành hai đoạn con và với .
Lượng khói tạo ra sẽ là:
- Kết quả cuối cùng: .
3. Các bước thực hiện
- Tiền xử lý: Xây dựng mảng cộng dồn (prefix sum) để tính nhanh tổng màu của một đoạn bất kỳ từ đến . Màu của đoạn sẽ là:
(sum[j] - sum[i-1]) % 100. - Khởi tạo: Tạo bảng kích thước , lấp đầy bằng một giá trị vô cùng lớn (infinity), các đường chéo chính .
- Lặp theo độ dài:
- Duyệt độ dài từ 2 đến .
- Duyệt điểm bắt đầu từ 1 đến .
- Xác định điểm kết thúc .
- Duyệt điểm chia từ đến để cập nhật theo công thức truy hồi ở trên.
4. Lưu ý khi triển khai
- Độ phức tạp: Thuật toán có độ phức tạp . Với , số phép tính khoảng , hoàn toàn chạy tốt trong giới hạn thời gian.
- Kiểu dữ liệu: Tổng lượng khói có thể lớn, nên sử dụng kiểu số nguyên 64-bit (
long longtrong C++ hoặc mặc định trong Python) để tránh tràn số. - Xử lý modulo: Khi tính màu đoạn , hãy đảm bảo kết quả của phép chia lấy dư không bị âm (trong C++, công thức an toàn là
(sum[j] - sum[i-1]) % 100nếu tổng luôn dương).