Processing math: 57%
Solutions of Jealousy - MarisaOJ: Marisa Online Judge

Solutions of Jealousy

Select solution language

Write solution here.


hoangbach2022    Created at    19 likes

# [Đọc lời giải full ở đây](https://hackmd.io/aRuWX_kZTKGuhmJoROv9Lg) ### Trạng thái quy hoạch động Đặt dp[i][j][k]: giá trị niềm vui lớn nhất đạt được tính đến ngày thứ i, người được ghé thăm ở ngày thứ ij (0 là Alice, 1 là Patchouli) và được ghé thăm liên tiếp k (1k2) lần. ### Trạng thái cơ sở: - dp[0][0][1]=A[0]: Marisa ghé thăm Alice vào ngày đầu tiên. - dp[0][1][1]=B[0]: Marisa ghé thăm Patchouli vào ngày đầu tiên. ### Công thức chuyển trạng thái: 1. Nếu Marisa ghé thăm Alice vào ngày i: - Nếu Marisa đã thăm Alice vào ngày i1, thì trạng thái sẽ chuyển sang thăm Alice lần thứ 2 liên tiếp: dp[i][0][2]=max - Nếu Marisa thăm Patchouli vào ngày i-1, thì trạng thái sẽ chuyển sang thăm Alice lần đầu tiên: dp[i][0][1] = \max(dp[i][0][1], \max(dp[i-1][1][1], dp[i-1][1][2]) + A_i) 2. Nếu Marisa ghé thăm Patchouli vào ngày i: - Nếu Marisa đã thăm Patchouli vào ngày i-1, thì trạng thái sẽ chuyển sang thăm Patchouli lần thứ 2 liên tiếp: dp[i][1][2] = \max(dp[i][1][2], dp[i-1][1][1] + B_i) - Nếu Marisa thăm Alice vào ngày i-1, thì trạng thái sẽ chuyển sang thăm Patchouli lần đầu tiên: dp[i][1][1] = \max(dp[i][1][1], \max(dp[i-1][0][1], dp[i-1][0][2]) + B_i) ### Kết quả: - Giá trị lớn nhất của niềm vui ở ngày cuối cùng sẽ là: \max(dp[n-1][0][1], dp[n-1][0][2], dp[n-1][1][1], dp[n-1][1][2])