# [Đọ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 \leq k \leq 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(dp[i][0][2], dp[i-1][0][1] + A_i) $$
- 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]) $$
hoangbach2022
Created at
9 likes