# [Đọ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ứ i là j (0 là Alice, 1 là Patchouli) và được ghé thăm liên tiếp k (1≤k≤2) 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 i−1, 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])