Hướng dẫn giải của HSG THPT TPHCM 2023 - Bắn tàu
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.
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.
Gọi ~dp[i][j]~ là số điểm bị trừ ít nhất khi đã bắn hết ~i~ tàu đầu tiên và đã dùng ~j~ tầm bắn. Xây dựng công thức quy hoạch động ta có:
$$dp[i][j] = min^{i}_{k = 1} ( dp[k - 1][j - 1] + max(a_k, a_{k + 1}, \ldots, a_i) * (i - k + 1) - (a_k + a_{k + 1} + \ldots + a_i))$$
Khởi tạo mảng ~dp~ ban đầu là ~\infty~, còn ~dp[0][0] = 0~.
Đán án của bài toán là ~dp[n][k + 1]~.
Tổng độ phức tạp cho bài toán là ~O(N^2 * K)~.
Bình luận
Cho mình hỏi tại sao không cho dp[i][k] = dp[i-1][k] + ... được ạ, kiểu ghép a[i] với đoạn trước đó luôn, nếu vậy độ phức tạp sẽ giảm xuống O(N^2). Mik làm cách đó nhưng không AC full test đc:((. Mn gthik giúp mik vs mik cảm ơn.
Mình không hiểu cái "+ ..." của bạn là sao nhưng mình bài này nếu bạn làm theo hiểu ghép luôn a[i] với cả đoạn trước đó luôn thì bạn sẽ phải tính lại hàm giá trị mà a[i] mang lại, ví dụ bạn ghép a[i] vào đoạn trước đó thì nếu a[i] trở thành số lớn nhất trong đoạn từ 1 tới i thì giá trị của đoạn [1,i] sẽ được tính lại mà chưa chắc việc bạn ghép vào sẽ thật sự mang lại giá trị tối ưu nhất. Mình thì không biết cách tối ưu làm sao để xuống còn O(N^2) nhưng mà ít ra sẽ phải có K ở trong độ phức tạp tại nó là ràng buộc của các bài toán con, thiếu nó sẽ không đi tới bước tiếp theo được, ví dụ bạn muốn chia 1 đoạn [l,r] thành 1 đoạn thì bạn ít nhất bạn sẽ có 2 lựa chọn
xét ban đầu có thể chọn bất kì nữa bạn
Sao kết quả là k + 1 vậy ạ
chắc tùy vào k của ông này bắt đầu từ đâu, nếu ông bắt đầu duyệt từ 1 ở vòng for 0->k thì sẽ là k, còn nếu duyệt từ 1->k thì k+1
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.