Editorial for HSG THPT TPHCM 2023 - Bắn tàu

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

Comments

Please read the guidelines before commenting.


  • 1
    nmhung29042009  commented on Aug. 7, 2025, 9:04 a.m.

    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.


    • 1
      Thaiutramku  commented on Aug. 16, 2025, 3:52 p.m.

      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

      • 1 là ghép cả đoạn [l,r] vào đoạn [1,l - 1] tức là sẽ không có bất kì hành động đổi mức năng lượng nào.
      • trường hợp 2 đó là bạn sẽ coi đoạn [l,r] là 1 đoạn mới (thay đổi năng lượng sao cho tối ưu với đoạn l,r) => dp[l][k] = max(cost(l,r) + dp[l - 1][k - 1]) trong đó: cost(l,r) = (r - l + 1)*max(a[l],...,a[r]) - sum(a[l],..,a[r]) => nên là dù thế nào vẫn phải tồn tại con K trong bài toán con để có thể tính bước tiếp theo. Đây là mình đang nói nếu hàm trạng thái dp của bạn giống với solution của người ta thoi ha.

  • 1
    Thaiutramku  commented on Sept. 8, 2024, 3:05 p.m.

    xét ban đầu có thể chọn bất kì nữa bạn


  • 0
    anhquan1btanson  commented on July 10, 2024, 2:46 p.m.

    Sao kết quả là k + 1 vậy ạ


    • -3
      dienthan901  commented on Oct. 13, 2024, 10:43 a.m.

      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


  • -36
    HoaBanMaTuy  commented on Nov. 26, 2023, 2:58 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.