Olympic Sinh Viên 2020 - Chuyên tin - Đường đi

View as PDF

Submit solution

Points: 0.80 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Olympic Sinh Viên
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Lưu ý: Đọc dữ liệu từ stdin, viết dữ liệu ra stdout.

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 19
    YugiHackerKhongCopCode   commented on Feb. 25, 2022, 6:24 p.m.

    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~?

    Hãy tiếp tục làm sai trước khi đọc spoil này

    Giống test trên nhưng ...