Olympic Sinh Viên 2021 - Chuyên tin - Cầu kính

Xem dạng PDF

Gửi bài giải

Điểm: 0,10 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M

Nguồn bài:
Olympic Sinh Viên
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -4
    song_hao_2910  đã bình luận lúc 31, Tháng 8, 2022, 5:00 sửa 4

    like


  • 6
    vnkiet  đã bình luận lúc 17, Tháng 6, 2022, 16:35

    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