Đọc lời giải full ở đây

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])$$