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
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.