Olympic Sinh Viên 2021 - Chuyên tin - CẦU KÍNH

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M

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

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


Comments

Please read the guidelines before commenting.



  • 0
    vnkiet   commented on June 17, 2022, 11:35 p.m.

    For everyone:

    Gọi dp[i][j] là số cách đi đến ô [j] tại hàng [i], với ô [1][j], chỉ có 2 cách đi là từ [1][j-1] hoặc [2][j-1], khi và chỉ khi ô đó là X, điều tương tự với ô [2][j].

    Công thức: dp[1][j] = dp[1][j-1]+dp[2][j-1], tương tự với dp[2][j]. Đáp án: dp[1][n]+dp[2][n].

    lưu ý sẽ có test sai với yêu cầu đề bài, do đó ta có trường hợp 2 xâu không cùng độ dài chuỗi. Bạn tự sửa nhé:)

    cách khởi tạo mảng dp trước khi tính toán bạn có thể tham khảo Atcoder Educational DP Contest H - Grid 1