-
Đánh giá : Đây là 1 bài tổng hợp khá nhiều kĩ thuật mới có thể AC !!!
-
Thuật toán : Quy hoạch động
- Gọi F[k][n] là chi phí bé nhất để chuyển thành k đống từ quặng 1 đến quặng n - Dễ thấy công thức sẽ là : F[k][n] = min ( f[k - 1][p - 1] + cost[p][n]). - Trong đó cost[p][n] là chi phí bé nhất để dồn các đống từ p đến n thành 1 đống ĐPT : O(k * n ^ 2 + n ^ 3) -
Cải tiến 1 : Tính mảng cost trong O(n * log(n)) thay vì O(n ^ 3)
- Nhận xét : (*) Gọi p là điểm tập hợp của đoạn [i, j] Gọi q là điểm tập hợp của đoạn [i, j + 1] Ta có thể chứng minh được q >= p (Dành cho các bạn tự chứng minh mình lười qué )) Từ đó ta có thể sử dụng chia để trị để tính đc mảng cost trong O(n * log(n)) -
Cải tiến 2 : Tính mảng F trong O(k * log(n)) thay vì O(k * n ^ 2)
- Cũng từ nhận xét (*) ta cũng có thể sử dụng chia để trị để tính mảng F trong O(n * log(n)) -
Làm đến đây là đã có thể AC (nếu bạn hên) hoặc như mình là sẽ bị 90 - 96 điểm vậy làm sao để AC nốt ?
-
Cải tiến 3 : Kĩ thuật 01
- Mình gọi cái này là Kĩ thuật 01 . Nó cũng thường xuyên được sử dụng trong các bài QHĐ - Nhận xét : F[i] chỉ phụ thuộc vào F[i - 1] nên ta có thế sử dụng mảng F[2][MAXN] - Về bản chất độ phức tạp sẽ không giảm nhưng bộ nhở sẽ giảm xuống và các bạn chắc chắn sẽ AC
End : Trên đây là lời giải của mình cho bài MINING. Có sai xót gì mong được góp ý. Happy Coding !!!