Bình luận

• 
  

  -2

  

  nakiri_ayame  đã bình luận lúc 4, Tháng 5, 2026, 14:49 ← chỉnh sửa →

  Mình thấy có nhiều bạn sử dụng thuật không chuẩn(stack) để AC bẩn bài này, nên mình xin đề xuất thêm 1 test:

  8
  2 2 2 3 3 2 2 2
  

  Đáp án là 5 (ghép a2 - a3, a6 - a7, rồi ghép các số 3 thành 4 rồi 5).

  Nhân đây thì mình xin trình bày hướng giải của mình:

  Vì với mỗi lần hợp 2 số, số mới chỉ tăng lên 1 đơn vị và ~a_i \le 40~ với ~N \le 262144 = 2^{18}~ nên giá trị lớn nhất ta có thể thể đạt được là 40 + 18 = 58

  Từ đó ta có được hàm quy hoạch động như sau: ~dp[v][i]~ là chỉ số nhỏ nhất ~j~ sao cho đoạn con từ ~i~ đến ~j~ khi hợp lại tạo ra được đúng một giá trị ~v~. Ta có công thức chuyển trạng thái như sau: $$ dp[v][i] = dp[v - 1][dp[v - 1][i] + 1] $$ với điều kiện ~dp[v][i]~ chưa tồn tại, ~dp[v - 1][i]~ và ~dp[v - 1][dp[v - 1][i] + 1]~ đã tồn tại. Công thức này có nghĩa là tìm ra hai đoạn liên tiếp bắt đầu từ i để tạo ra 2 giá trị ~v - 1~ để hợp lại tạo ra ~v~. Ban đầu khởi tạo dp bằng -1 nghĩa là không tồn tại, trường hợp cơ sở ~dp[a[i]][i] = i (1 \le i \le N)~. Đáp án sẽ là giá trị ~v~ lớn nhất sao cho ~dp[v][i]~ tồn tại.

  Code mẫu

  P/S: Code có thời gian chạy nhanh nhất thậm chí chỉ duyệt 1 chiều xuôi, nên chỉ cần test 4 2 2 2 3 là code này sai ::)

• 
  

  -20

  

  Xcode  đã bình luận lúc 31, Tháng 7, 2023, 9:35

  b này 1 đấm

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.