Bình luận

• 
  

  29

  

  YugiHackerKhongCopCode  đã bình luận lúc 25, Tháng 2, 2022, 11:24 ← chỉnh sửa →

  Spoil!

  1, Version dễ hơn

  https://codeforces.com/contest/2/problem/B

  Thuật toán:

  Chỉ cần quan tâm đến số lượng nhân tử ~2~ và ~5~ trong số ~a[i][j]~, gọi là ~cnt2[i][j]~ và ~cnt5[i][j]~.

  1, Trường hợp không xét số ~0~:

  Gọi ~f2[i][j]~ và ~f5[i][j]~ là số lượng nhân tử ~2~ và ~5~ nhỏ nhất trên đường đi từ ô ~[1, 1]~ đến ô [~n, m~]

  Công thức:

  $$f[i][j] = min(f[i-1][j], f[i][j-1]) + cnt[i][j];$$

  (Có xét thêm chút điều kiện)

  Gọi ~Min~ ~=~ ~min(f2[n][m], f5[n][m])~, đường đi từ ~i~ đến ~j~ không thể ít hơn ~Min~ số ~0~ (vì không có con đường nào ít hơn ~Min~ số ~2~ và ~5~)

  ~=>~ Con đường dẫn tới kết quả là Min chính là đường có ít chữ số 0 nhất

  2, Trường hợp xét số 0:

  Nếu đi qua số ~0~ ~=>~ Kết quả luôn luôn là ~1~, vì vậy để các con đường ở trường hợp ~1~ đi qua số ~0~, đặt ~cnt2[i][j] = cnt5[i][j] = \infty~

  3, Truy vết:

  Trường hợp 1: Truy vết ngược lại mảng ~f2~ hoặc ~f5~ tùy theo con đường nào nhỏ hơn

  Trường hợp 2: Lưu lại vị trí của điểm bằng ~0~ trong mảng, đi qua tọa độ điểm đó để đến ô [~n, m~]

  2, Tối ưu đường đi trong bài này

  1, Trường hợp 1:

  Tối ưu đường đi sẽ được xử lý trong phần truy vết, và được làm theo thứ tự ngược lại, nên ta phải đảo ngược cách quy hoạch động (tính từ [~n, m~] về [~1, 1~]), ưu tiên chọn đường có chữ 'D' trước 'L'.

  2, Trường hợp 2: (Nghĩ trước khi đọc spoil tiếp theo)

  Ưu tiên 'D' trước 'L', nên mình phải chọn số ~0~ có chỉ số hàng lớn nhất có thể

  Hãy làm sai trước khi đọc spoil này

  Nếu ô ~[1, 1] = 0~?

  Nếu ô ~[?, ?] = 0~?